Laiko ribojimas: 1s

Atminties ribojimas: 256MB

Duomenų failas: troleibusas.in

Rezultatų failas: troleibusas.out

Jei norite pateikti savo sprendimą - prisijunkite.

Troleibusas

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 n (1\\leqn\\leq2\\times10^5) - užklausų skaičius.

Tolesnėse n eilučių yra pateiktos užklausos, po vieną kiekvienoje eilutėję. Užklausa aprašoma simboliu p, g, arba i, ir skaičiumi a_i (1\\leqa_i\\leq10^5). Užklausa p reiškia kad keleivis kurio numeris yra a_i į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

Pradiniai duomenys Rezultatai Paaiškinimas
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