Задано підвішене дерево, яке містить 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.

Вихідні дані

Виведіть у вихідний файл суму номерів вершин - відповідей на усі запити.