Общий предок - 2
Общий предок - 2
Задано подвешенное дерево, содержащее n (1 ≤ n ≤ 105
) вершин, пронумерованных от 0 до n - 1. Требуется ответить на m (1 ≤ m ≤ 107
) запросов о наименьшем общем предке для пары вершин.
Запросы генерируются следующим образом. Заданы числа 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
1 2 0 0 1 1 1
0