- Time limit: 4.00 s
- Memory limit: 128 MB
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$
Syöte:
5
1 1 3 3
5
4 2
2 1
5 3
1 1
5 1
Tuloste:
1
1
QAQ
QAQ
3