I. LCA за константу

Та же задача, что в B, но запросов до десяти миллионов, а ограничение времени вдвое меньше. Логарифм на запрос больше не проходит.

Формат тот же, что в задаче B: $n$ и $m$ ($1 \le n \le 10^5$, $1 \le m \le 10^7$), затем $n-1$ родителей, затем $a_1$, $a_2$ и $x$, $y$, $z$. Запрос зависит от предыдущего ответа.

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