CSES - Henkilöstö
  • Time limit: 4.00 s
  • Memory limit: 128 MB

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 nn: työntekijöiden määrä. Työntekijät on numeroitu 1,2,,n1,2,\ldots,n, ja työntekijä 1 on Uolevin setä (yrityksen johtaja).

Sitten syötteessä on n1n-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 nn asti. Uolevin sedällä ei ole esimiestä.

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

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

Tuloste

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

Rajat

  • 1n51041 \le n \le 5\cdot 10^4
  • 1q1051 \le q \le 10^5
  • 1xn1 \le x \le n
  • 1k51041 \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