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

LCA Problem Revisited

LCA Problem Revisited

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

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

Запросы генерируются следующим образом. Заданы числа 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