Šeštadieninė informatikos olimpiadininkų mokykla

Troleibusas turi dvejas duris per kurias gali įlipti keleiviai - vienas priekyje, ir kitas gale. Troleibusas yra labai siauras, ir jame keleiviai net negali prasilenkti - jei keleivis nori išlipti pro kažkurias duris, tai visi keleiviai esantys tarp jo ir durų turi išlipti kad jį praleistų. Tie keleiviai kurie išlipa kad praleistų kitus nelaukia kol vėl galės įlipti - jie tiesiog įlipa pro kitas autobuso duris (tokia pačia tvarka kaip ir išlipo).

Norėdamas išlipti keleivis visada renkasi artimesnes duris (tarp kurių ir jo yra mažiausiai kitų keleivių). Jei abiejos durys yra tokiu pačiu atstumu, tai jis išlipa per priekines.

Pradžioje troleibusas yra tuščias. Jūs turite sąrašą užklausų kurios nurodo kada kurie keleiviai įlipa ir išlipa. Kiekvienam išlipančiam keleiviui turite pasakyti ar jis išlips pro priekines, ar pro galines duris.

Pradiniai duomenys

Pirmoje eilutėje yra skaičius () - užklausų skaičius.

Tolesnėse eilučių yra pateiktos užklausos, po vieną kiekvienoje eilutėję. Užklausa aprašoma simboliu p, g, arba i, ir skaičiumi (). Užklausa p reiškia kad keleivis kurio numeris yra įlipo pro priekines duris, g - įlipo pro galines duris, o i - keleivis išlipa iš troleibuso.

Kiekvienai išlipimo užklausai garantuota kad tas keleivis yra troleibuse, ir joks keleivis neįlips į troleibusą daugiau nei vieną kartą.

Rezultatai

Kiekvienai i tipo užklausai išspausdinkite "priekines", jei keleivis išlips per priekines duris, arba "galines", jei išlips per galines.

Pavyzdžiai

6
p 1
p 2
p 3
p 4
i 3
i 4

priekines
galines

Po kiekvienos užklausos troleibuso keleiviai bus tokie (priekis dešinėje):
1
1 2
1 2 3
1 2 3 4
4 1 2
1 2