L. Миллион в шестидесяти четырёх мегабайтах

Снова наименьший общий предок: до миллиона вершин, до миллиона запросов. Памяти — шестьдесят четыре мегабайта, времени — секунда.

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

В первой строке $n$ и $m$ ($1 \le n \le 10^6$, $1 \le m \le 10^6$). Во второй строке $n-1$ родителей. В третьей — $a_1$ и $a_2$, в четвёртой — $x$, $y$, $z$.

$i$-й запрос — пара $(a_{2i-1}, a_{2i})$, без поправки на предыдущий ответ.

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