Laiko ribojimas: 0.5s

Atminties ribojimas: 64MB

Jei norite pateikti savo sprendimą - prisijunkite.

Blyninė

Algis yra vyriausiasis šefas garsiausioje Lietuvos blyninėje. Jo blynai yra ypatingi, nes kiekvienas iš jų turi vieną išskirtinį akcentą - sirupu užrašytą žodį. Šįryt į Algio blyninę atbėgo daugybė vaikų, tiesiog laukiančių nesulaukiančių paragauti gardžiųjų blynų. Kiekvienu laiko momentu įvyksta vienas iš dviejų įvykių: arba Algis iškepa blyną su tam tikru užrašytu žodžiu ir deda jį į krūvos viršų, arba kuris nors vaikas paima viršutinį blyną iš krūvos (jei krūva netuščia) ir jį suvalgo.

Jums duotas vienos dienos įvykių sąrašas. Jūsų užduotis - kiekvienąkart, kai kuris nors vaikas ateina ir nori suvalgyti blyną, rasti, koks žodis bus parašytas ant jo, arba nustatyti, kad blynų lėkštė tuščia ir tas vaikas blyno negaus. Dienos pradžioje blynų lėkštė yra tuščia.

Pastaba. Atkreipkite dėmesį į didelę įvesties ir išvesties apimtį.

Pradiniai duomenys

Pirmoje eilutėje įvestas vienas sveikasis skaičius n - įvykių kiekis (1\\leqn\\leq3\\cdotp10^5).

Toliau seka n eilučių. Jei i-uoju laiko momentu Algis iškepė blyną su užrašu s, tai i-ojoje eilutėje bus įrašyta \\texttt{bums}. Kitu atveju i-ojoje eilutėje bus įrašyta \\texttt{niam} - tai reiškia, kad šiuo laiko momentu kažkuris vaikas atėjo suvalgyti blyno.

Yra garantuota, kad kiekvienas ant blyno užrašytas žodis susideda tik iš mažųjų lotyniškos abėcėlės raidžių, o žodžio ilgis yra tarp 1 ir 30 simbolių.

Rezultatai

Kiekvienai \\texttt{bum} tipo užklausai jūsų programa turi išspausdinti žodį, kuris užrašytas ant suvalgyto blyno. Jei šiuo laiko momentu blynų lėkštė tuščia, programa turi išvesti ":(" (be kabučių).

Pavyzdžiai

Pradiniai duomenys Rezultatai
10
bum pirmas
bum antras
niam
bum trecias
niam
niam
niam
bum ketvirtas
niam
bum penktas
antras
trecias
pirmas
:(
ketvirtas

Paaiškinimas

Iš pradžių blynų lėkštė yra tuščia. Kiekvieno įvykio aprašymai:

  1. \\texttt{bumpirmas} - ant lėkštės padedams blynas su užrašu "pirmas". Lėkštė atrodo taip: \\texttt{pirmas}
  2. \\texttt{bumantras} - ant lėkštės padedamas blynas su užrašu "antras". Lėkštė atrodo taip: \\texttt{pirmas},\\texttt{antras}
  3. \\texttt{niam} - lėkštės viršuje yra blynas su užrašu "antras". Vaikas jį suvalgo ir lėkštė lieka tokia: \\texttt{pirmas}
  4. \\texttt{bumtrecias} - ant lėkštės padedamas blynas su užrašu "trecias". Lėkštė atrodo taip: \\texttt{pirmas},\\texttt{trecias}
  5. \\texttt{niam} - lėkštės viršuje yra blynas su užrašu "trecias". Vaikas jį suvalgo ir lėkštė lieka tokia: \\texttt{pirmas}
  6. \\texttt{niam} - lėkštės viršuje yra blynas su užrašu "pirmas". Vaikas jį suvalgo ir lėkštė lieka tuščia
  7. \\texttt{niam} - lėkštė yra tuščia, tad vaikui nėra ką valgyti :(
  8. \\texttt{bumketvirtas} - ant lėkštės padedamas blynas su užrašu "ketvirtas". Lėkštė atrodo taip: \\texttt{ketvirtas}
  9. \\texttt{niam} - lėkštės viršuje yra blynas su užrašu "ketvirtas". Vaikas jį suvalgo ir lėkštė lieka tuščia
  10. \\texttt{bumpenktas} - ant lėkštės padedamas blynas su užrašu "penktas". Lėkštė atrodo taip: \\texttt{penktas}