Ümumi əcdad - 2#3299
Verilmiş n~(1 \le n \le 10^5) təpədən ibarət kök ağac verilir, təpələr -dan n - 1-ə qədər nömrələnib. m~(1 \le m \le 10^7) sorğunu emal etmək tələb olunur — hər sorğu bir cüt təpə üçün ən kiçik ümumi əcdadı (LCA) tapmaqdan ibarətdir.
Sorğular aşağıdakı qaydada generasiya edilir. a_1, a_2 qiymətləri, həmçinin və ədədləri verilir. i \ge 3 üçün a_i qiymətləri aşağıdakı düsturla hesablanır:
Birinci sorğu (a_1, a_2) şəklindədir. Tutaq ki, (i-1)-ci sorğunun cavabı -dir. Onda -ci sorğu aşağıdakı kimi təyin edilir:
Birinci sətirdə iki tam ədəd və verilir. Ağacın kökünün nömrəsi -dır.
İkinci sətirdə n - 1 tam ədəd verilir: onların -cisi i~(1 \le i \le n - 1) təpəsinin valideyninin nömrəsinə bərabərdir.
Üçüncü sətirdə iki tam ədəd a_1 və a_2~(0 \le a_1, a_2 < n) verilir.
Dördüncü sətirdə üç tam ədəd və z~(0 \le x, y, z \le 10^9) verilir.
Bütün sorğulara cavab olan təpələrin nömrələrinin cəmini çap edin.
Nümunə 1
Nümunə 2