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

Mugur a primit 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:

• push x. Numărul x se adaugă în stivă (x devine elementul din vârful stivei).
• 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.
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.

Cerința

Ca să nu se plictisească, Mugur își pune zilnic câte o întrebare: având doar operațiile până în ziua curentă, dacă le execută în ordinea indicilor, care ar fi elementul de pe vârful stivei?

Date de intrare

Fișierul de intrare mugur.in 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 push, reprezentând numărul care se introduce în stivă.

Date de ieșire

Fișierul de ieșire mugur.out va conține N linii, pe fiecare linie fiind un singur număr întreg: 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 \le N \le 100000\)
• \(1 \le {x}_{i} \le 10^9\)
• \(s_i \in \{push, pop\}\)
• \(1 \le p_i \le 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.

Punctare

• 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 push.
• Pentru alte teste în valoare de 8 puncte, \(N \le 5000\).
• Pentru alte teste în valoare de 13 puncte, toate operațiile push apar înaintea operațiilor pop.
• Pentru alte teste în valoare de 69 de puncte, nu există restricții suplimentare.

Exemplu 1:

mugur.in

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

mugur.out

2
-1
2
3

Explicație

După prima zi, avem operațiile: push 2 → vârful stivei este 2.

După a doua zi, avem operațiile: push 2, pop → stiva este goală.

După a treia zi, avem operațiile: push 2, push 3, pop → vârful stivei este 2.

După a patra zi, avem operațiile: push 2, push 3, push 4, pop → vârful stivei este 3.

Exemplu 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

După prima zi, avem operațiile: pop → stiva este goală.

După a doua zi, avem operațiile: pop, push 7 → vârful stivei este 7.

După a treia zi, avem operațiile: pop, push 9, push 7 → vârful stivei este 7.

După a patra zi, avem operațiile: pop, push 9, push 7, pop → vârful stivei este 9.

După a cincea zi, avem operațiile: pop, push 9, push 5, push 7, pop → vârful stivei este 5.

După a șasea zi, avem operațiile: pop, push 9, push 5, push 7, pop, pop → vârful stivei este 9.

După a șaptea zi, avem operațiile: pop, push 9, push 5, push 7, pop, pop, pop → stiva este goală.