intalnire

În orașul programatorilor există un local celebru unde lumea se poate distra cât dorește, la orice oră. Primarul orașului programatorilor a construit, pornind de la acest local, mai multe străzi către casele tuturor cetățenilor, case codificate cu numere de la $2$ la $n$, localul fiind codificat cu $1$. Dacă între o casă și local nu există alte case, atunci drumul este construit direct între cele două imobile, dar dacă între casă și local există și alte case, atunci drumul va fi format din drumul de la local la prima casă, apoi se va construi drumul de la prima casă la a doua casă, apoi de la a doua casă la a treia casă și tot așa până se ajunge la casa curentă.

Orașul este codificat sub forma unui vector $t[\ ]$, unde $t[i] = 0$ dacă imobilul $i$ este exact localul unde se pot distra oamenii din oraș sau $t[i] = y$, cu $y \neq 0$, cu semnificația că de la casa $i$ se poate ajunge la casa/imobilul $y$ care se află între local și casa curentă.

Andrei și Alexandru sunt locuitori ai acestui oraș. Ei stau la casele cu codul $x_1$, respectiv $x_2$. Ei doresc să se întâlnească în drum spre local unde se vor distra, prin urmare doresc să alfe care este prima casă la care pot amândoi să ajungă, în drum spre local.

Cerința

Pentru $q$ întrebări de forma "care este prima casă unde Andrei și Alexandru se pot întâlni, dacă aceștia locuiesc la casele $x_1$ și $x_2$?", să se alfe răspunsul la aceste întrebări.

Date de intrare

Pe prima linie se vor găsi numerele $n$ și $q$. Pe a doua linie se va găsi vectorul $t[\ ]$, cu semnificația din enunț, pentru toți indicii de la $2$ la $n$. Pentru $i = 1$, se consideră $t[i] = 0$.
Pe următoarele $q$ linii se vor găsi câte două numere $x_1$ și $x_2$, cu semnificația din enunț.

Date de ieșire

Se va afișa răspunsul pentru fiecare întrebare, pe linii diferite.

Restricții și precizări

• $1 \leq n \leq 100 \ 000$;
• $1 \leq q \leq 4 \ 000 \ 000$;
• Există exact un drum de la local la fiecare casă din orașul programatorilor.
• Este recomandat să folosiți citirea rapidă cu aceste linii de cod la începutul funcției main(): cin.tie(0)->sync_with_stdio(0);.

Exemplu

stdin

5 2
1 1 2 2
1 2
4 5

stdout

1
2