Wstęp do programowania w C++

Tym razem do egzaminu z informatyki podeszło bardzo dużo studentów (nie więcej niż 200 000). Niektórzy zdający bardzo sprawnie odpowiedzieli na wszystkie pytania i wcześniej oddali karty odpowiedzi, dzięki czemu profesor Algobit mógł już w trakcie egzaminu sprawdzić niektóre prace. Studenci odkładali prace na biurko profesora kładąc je na stos już leżących prac. Prace, które profesor sprawdzał były zawsze brane z wierzchołka stosu.

Napisz program symulujący daną sytuację.

Input

W pierwszym wierszu jedna liczba określająca ilość zapytań.

Każde zapytanie składa się z następujących informacji:

[+] [pierwsza litera nazwiska studenta] - dany student odkłada pracę na stos

[-] - profesor bierze prace ze stosu do sprawdzenia 

Output

dla zapytania [-], należy wypisać literę jaką ma przyporządkowany student, którego praca będzia sprawdzana lub napis [empty], w przypadku, gdy na biurku nie ma prac.

Example

Input:
10
+ A
+ B
+ C
+ D
-
-
-
-
-
-
Output:
D
C
B
A
empty
empty