Спільний предок - 2#3299
Задано вкорінене дерево, що містить n~(1 \le n \le 10^5) вершин, пронумерованих від до n - 1. Потрібно обробити m~(1 \le m \le 10^7) запитів на знаходження найменшого спільного предка (LCA) для пар вершин.
Запити генеруються наступним чином. Задано значення a_1, a_2, а також числа та . Для i \ge 3 значення a_i обчислюються за формулою:
Перший запит має вигляд (a_1, a_2). Нехай відповідь на (i-1)-й запит дорівнює . Тоді -й запит задається як
Перший рядок містить два цілих числа та . Корінь дерева має номер .
Другий рядок містить n - 1 цілих чисел: -е з них дорівнює номеру батька вершини i~(1 \le i \le n - 1).
Третій рядок містить два цілих числа a_1 та a_2~(0 \le a_1, a_2 < n).
Четвертий рядок містить три цілих числа та z~(0 \le x, y, z \le 10^9).
Виведіть суму номерів вершин, що є відповідями на всі запити.
Приклад 1
Приклад 2