Šeštadieninė informatikos olimpiadininkų mokykla

Kamuoliukų automatą galime pavaizduoti šakniniu medžiu. Medžio viršūnės sunumeruotos nuo 1 iki N. Kiekviena viršūnė yra arba tuščia arba joje yra vienas kamuoliukas. Pradiniu momentu visos viršūnės yra tuščios. Kai automatas paleidžiamas, jis gali atlikti dviejų tipų veiksmus:

1. Į automatą įdėti k kamuoliukų. Kamuoliukai po vieną dedami į šakninę viršūnę. Jei viršūnėje yra kamuoliukas ir ji turi nors vieną tuščią vaikinę viršūnę, kamuoliukas nuriedą į tą tuščią vaikinę viršūnę, kurios pomedis turi viršūnę su mažiausiu numeriu. Pavyzdžiui, jei į žemiau esančiame paveiksle pavaizduotą automatą įmesime du kamuoliukus, jie nuriedės į viršūnes 1 ir 3: abu kamuoliukai riedės iš 4-os viršūnės į 3-ią, nes ši yra tuščia ir jos pomedyje yra viršūnė, kurios numeris 1; pirmasis kamuoliukas iš 3-ios viršūnės nuriedės į 1-ą.

2. Pašalinti kamuoliuką iš konkrečios viršūnės. Viršūnė tampa tuščia, o aukščiau esantys kamuoliukai (jeigu tokių yra) rieda žemyn. Jeigu tuščios viršūnės tėvinėje viršūnėje yra kamuoliukas, jis būtinai riedės žemyn. Pavyzdžiui, jei žemiau pateiktame pavyzdyje pašalintume kamuoliukus 5, 7 ir 8 iš viršūnių šia tvarka, tai po pašalinimo liktų tuščios viršūnės 1, 2 ir 3.

Pradiniai duomenys

Pirmoje eilutėje įrašyti du sveikieji skaičiai N ir Q – medžio viršūnių ir veiksmų skaičiai. Tolesnės N eilučių nusako kamuoliukų automatą. Kiekvienoje šių eilučių įrašytas vienas sveikasis skaičius reiškiantis viršūnės numerį: i-ojoje šių eilučių įrašytas i-osios viršūnės tėvinės viršūnės numeris arba 0, jei i-oji viršūnė yra medžio šaknis. Kiekvienoje tolesnių Q eilučių įrašyti du sveikieji skaičiai, apibūdinantys veiksmą, kurį reikės atlikti. 1-o tipo veiksmas žymimas 1 k kur k lygus į mašiną įdedamų kamuoliukų skaičiui. 2-o is tipo veiksmas žymimas 2 x kur x yra viršūnės iš kurios šalinamas kamuoliukas, numeris.

Visi duomenyse pateikti veiksmai yra korektiški: nereikės įdėti į automatą daugiau kamuoliukų nei yra tuščių viršūnių, taip pat nereikės šalinti kamuoliuko iš tuščios viršūnės.

Rezultatai

Kiekvienam 1-o tipo veiksmui reikia išvesti viršūnės, į kurią nuriedės paskutinysis tuo veiksmu įmestas kamuoliukas, numerį. Kiekvienam 2-o tipo veiksmui reikia išvesti skaičių kamuoliukų, riedėjusių žemyn po to kai buvo atliktas šis veiksmas (kamuoliuko išėmimas).

Ribojimai

Pavyzdžiai

8 4
0
1
2
2
3
3
4
6
1 8
2 5
2 7
2 8

1
3
2
2