J. Миллион вершин

Та же задача про наименьшего общего предка, но вершин и запросов до миллиона, а памяти — сто двадцать восемь мегабайт.

Запросы порождаются формулой и не зависят от ответов: пары известны заранее.

В первой строке $n$ и $m$ ($1 \le n \le 10^6$, $1 \le m \le 10^6$). Во второй строке $n-1$ чисел — родители вершин от $1$ до $n-1$.

В третьей строке $a_1$ и $a_2$, в четвёртой — $x$, $y$, $z$ ($0 \le x, y, z \le 10^9$).

Числа порождаются правилом $a_i = (x \cdot a_{i-2} + y \cdot a_{i-1} + z) \bmod n$; $i$-й запрос — пара $(a_{2i-1}, a_{2i})$ без поправки на предыдущий ответ.

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