Uolevin sedän yritys on kasvanut vuosien aikana, ja nyt yrityksen palveluksessa on suuri määrä työntekijöitä. Tämän vuoksi henkilöstön rakenteen hahmottaminen alkaa olla vaikeaa. Voisitko auttaa?

Syöte

Syötteen ensimmäisellä rivillä on kokonaisluku n: työntekijöiden määrä. Työntekijät on numeroitu 1,2,\ldots,n, ja työntekijä 1 on Uolevin setä (yrityksen johtaja).

Sitten syötteessä on n-1 lukua, jotka kertovat, kuka on kunkin työntekijän esimies. Ensin tulee työntekijä 2:n esimies, sitten työntekijä 3:n esimies jne. työntekijään n asti. Uolevin sedällä ei ole esimiestä.

Tämän jälkeen syötteessä on luku q: kyselyiden määrä.

Lopuksi syötteessä on q riviä, joista jokainen kuvaa yhden kyselyn. Kullakin rivillä on kaksi kokonaislukua x ja k. Tehtävänä on selvittää, kuka on k tasoa ylempänä työntekijää x yrityksessä.

Tuloste

Ohjelmasi tulee tulostaa vastaus jokaiseen kyselyyn. Jos kysytty esimies on olemassa, tulosta sen numero, ja muuten QAQ.

Rajat

• 1 \le n \le 5\cdot 10^4
• 1 \le q \le 10^5
• 1 \le x \le n
• 1 \le k \le 5\cdot 10^4

Esimerkki

Syöte:

5
1 1 3 3
5
4 2
2 1
5 3
1 1
5 1

Tuloste:

1
1
QAQ
QAQ
3