LCA Problem Revisited (Easy)
LCA Problem Revisited (Easy)
Задано підвішене дерево, яке містить n (1 ≤ n ≤ 100) вершин, пронумерованих від 0 до n - 1. Потрібно відповісти на m (1 ≤ m ≤ 100) запитів про найменшого спільного предка для пари вершин.
Запити генеруються наступним чином. Задано числа a1
, a2
та числа x, y і z. Числа a3
, ..., a2m
генерються наступним чином: ai
= (x · ai-2
+ y · ai-1
+ z) mod n. Перший запит має вид < a1
, a2
>. Якщо відповідь на i - 1-й запит дорівнює v, то i-й запит має вид < (a2i-1
+ v) mod n, a2i
>.
Вхідні дані
Перший рядок містить два числа n та m. Корінь дерева має номер 0. Другий рядок містить n - 1 цілих чисел, i-е з цих чисел рівне номеру предка вершини i. Третій рядок містить два цілих числа у діапазоні від 0 до n - 1: a1
та a2
. Четвертий рядок містить три цілих числа: x, y та z, ці числа невід'ємні і не перевищують 109
.
Вихідні дані
Виведіть суму номерів вершин - відповідей на усі запити.
3 2 0 1 2 1 1 1 0
2