LCA Problem Revisited#5218
Задано підвішене дерево, яке містить (1 \leq n \leq 100\,000) вершин, пронумерованих від до n-1. Потрібно відповісти на (1 \leq m \leq 10\,000\,000) запитів про найменшого спільного предка для пари вершин.
Запити генеруються наступним чином. Задано числа a_1, a_2, а також числа , , . Числа a_3, \ldots, a_{2m} генеруються так: a_i = (x \cdot a_{i-2} + y \cdot a_{i-1} + z) \bmod n. Перший запит має вигляд \langle a_1, a_2 \rangle. Якщо відповідь на (i-1)-й запит дорівнює , то -й запит має вигляд \langle (a_{2i-1} + v)\bmod n,\, a_{2i} \rangle.
Перший рядок містить два числа: та . Корінь дерева має номер .
Другий рядок містить n - 1 цілих чисел, -те з цих чисел дорівнює номеру батька вершини .
Третій рядок містить два цілих числа у діапазоні від до n - 1: a_1 та a_2.
Четвертий рядок містить три цілих числа: , , ; ці числа невід'ємні і не перевищують 10^9.
Виведіть суму номерів вершин — відповідей на усі запити.
Приклад 1