e-olymp
Competitions

ADA University - February 12 - LCA

LCA - 2

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

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

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

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

Time limit 4 seconds
Memory limit 128 MiB
Input example #1
3 2
0 1
2 1
1 1 0
Output example #1
2
Input example #2
1 2

0 0
1 1 1
Output example #2
0