eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач
Задачи

Общий предок - 2

Общий предок - 2

Лимит времени 6 секунд
Лимит использования памяти 128 MiB

Задано подвешенное дерево, содержащее n (1n10^5) вершин, пронумерованных от 0 до n - 1. Требуется ответить на m (1m10^7) запросов о наименьшем общем предке для пары вершин.

Запросы генерируются следующим образом. Заданы числа a[1], a[2] и числа x, y и z. Числа a[3], ..., a[2m] генерируются следующим образом:

a[i] = (x * a[i-2] + y * a[i-1] + z) mod n

Первый запрос имеет вид (a[1], a[2]). Если ответ на (i - 1)-ый запрос равен v, то i-ый запрос имеет вид ((a[2i-1] + v) mod n, a[2i]).

Входные данные

Первая строка содержит два числа n и m. Корень дерева имеет номер 0. Вторая строка содержит n - 1 целых чисел, i-е из этих чисел равно номеру родителя вершины i. Третья строка содержит два целых числа в диапазоне от 0 до n - 1: a[1] и a[2]. Четвертая строка содержит три целых числа: x, y и z, эти числа неотрицательны и не превосходят 10^9.

Выходные данные

Выведите сумму номеров вершин - ответов на все запросы.

Пример

Входные данные #1
3 2
0 1
2 1
1 1 0
Выходные данные #1
2
Входные данные #2
1 2

0 0
1 1 1
Выходные данные #2
0