Mugur

La mulți ani, Mugur! Să trăiești 1 000 000 de ani!

Mugur a primit un cadou de ziua sa de la fiul său Mugurel o stivă. După ce chefuiește cu prietenii la Căminul Cultural din Imperiul Rațelor de Cauciuc, el merge acasă entuziasmat și începe să facă operații pe ea.

Operațiile sunt de două tipuri:

• $\text{push } x$ — Numărul $x$ se adaugă în stivă ($x$ devine elementul din vârful stivei).
• $\text{pop}$ — Se elimină elementul din vârful stivei. Dacă stiva este goală, operația nu are niciun efect.

Din păcate, stiva nu era cea mai calitativă, așa că după ce face $N$ operații pe ea, aceasta dă eroarea maCmAcMac și nu mai poate să execute alte operații.

Cerință

Fiind o rață bătrână, Mugur nu reușește să-și amintească instant toate operațiile pe care le-a făcut, însă în fiecare zi își aduce aminte de câte o operație și a câta era aceasta în șirul inițial de operații. Ca să nu se plictisească, el își pune zilnic câte o întrebare: având doar operațiile până în ziua curentă, dacă le executăm în ordinea indicilor, care ar fi elementul de pe vârful stivei?

Date de intrare

Fișierul de intrare va conține pe prima linie un număr întreg $N$, reprezentând numărul de operații.

Fiecare linie $i$ din următoarele $N$ linii conține câte o operație: un număr natural $p_i$ reprezentând indicele operației, un șir de caractere $s_i$ reprezentând tipul operației și un număr natural $x_i$ dacă operația este de tip $\text{push}$, reprezentând numărul care se introduce în stivă.

Date de ieșire

Fișierul de ieșire va conține $N$ linii, pe fiecare linie fiind un singur număr natural: elementul de pe vârful stivei luând în considerare operațiile curente sau -1 dacă stiva este goală.

Restricții și precizări

• $1 \leq N \leq 100 \ 000$
• $1 \leq x_i \leq 10^9$
• $s_i \in \{ \text{push}, \text{pop} \}$
• $1 \leq p_i \leq N$
• Toți indicii operațiilor care apar sunt distincți.
• Toate numerele sunt întregi.
• Mugurel își cere scuze pentru inconveniențe, data viitoare va cumpăra un cadou mai calitativ.
• Pentru teste în valoare de $5$ puncte, indicii operațiilor sunt în ordine crescătoare.
• Pentru alte teste în valoare de $5$ puncte, toate operațiile sunt de tip $\text{push}$.
• Pentru alte teste în valoare de $8$ puncte, $N \leq 5 \ 000$.
• Pentru alte teste în valoare de $13$ puncte, toate operațiile $\text{push}$ apar înaintea operațiilor $\text{pop}$.
• Pentru alte teste în valoare de $69$ de puncte, nu există restricții suplimentare.

Exemplul 1

mugur.in

4
1 push 2
4 pop
2 push 3
3 push 4

mugur.out

2
-1
2
3

Explicație

În acest exemplu, avem următoarele operații după fiecare zi:

• După prima zi, avem operațiile: $\text{push} \ 2$. Vârful stivei este $2$.
• După a doua zi, avem operațiile: $\text{push} \ 2$, $\text{pop}$. Stiva este goală.
• După a treia zi, avem operațiile: $\text{push} \ 2$, $\text{push} \ 3$, $\text{pop}$. Vârful stivei este $2$.
• După a patra zi, avem operațiile: $\text{push} \ 2$, $\text{push} \ 3$, $\text{push} \ 4$, $\text{pop}$. Vârful stivei este $3$.

Exemplul 2

mugur.in

7
1 pop
4 push 7
2 push 9
5 pop
3 push 5
6 pop
7 pop

mugur.out

-1
7
7
9
5
9
-1

Explicație

În acest exemplu, avem următoarele operații după fiecare zi:

• După prima zi, avem operațiile: $\text{pop}$. Stiva este goală.
• După a doua zi, avem operațiile: $\text{pop}$, $\text{push} \ 7$. Vârful stivei este $7$.
• După a treia zi, avem operațiile: $\text{pop}$, $\text{push} \ 9$, $\text{push} \ 7$. Vârful stivei este $7$.
• După a patra zi, avem operațiile: $\text{pop}$, $\text{push} \ 9$, $\text{push} \ 7$, $\text{pop}$. Vârful stivei este $9$.
• După a cincea zi, avem operațiile: $\text{pop}$, $\text{push} \ 9$, $\text{push} \ 5$, $\text{push} \ 7$, $\text{pop}$. Vârful stivei este $5$.
• După a șasea zi, avem operațiile: $\text{pop}$, $\text{push} \ 9$, $\text{push} \ 5$, $\text{push} \ 7$, $\text{pop}$, $\text{pop}$. Vârful stivei este $9$.
• După a șaptea zi, avem operațiile: $\text{pop}$, $\text{push} \ 9$, $\text{push} \ 5$, $\text{push} \ 7$, $\text{pop}$, $\text{pop}$, $\text{pop}$. Stiva este goală.