Nitish has challenged Mahesh to a memory contest. The challenge is as follows. Nitish will ask Mahesh to remember 10-letter words and later answer queries on the words he has memorized. The commands as are follows:

1) learn: This command is used by Nitish to ask Mahesh to remember a word. Mahesh must add this word to the list of his remembered words.

2) reportsmallest: This command is used by Nitish to ask for the lexicographically smallest word from the words that Mahesh currently knows.

3) forgetsmallest: This command is used by Nitish to ask Mahesh to forget the lexicographically smallest word. Essentially, Mahesh must delete this word from his dictionary.

Mahesh has asked for your help in this task. You are required to design and implement a suitable data structure which supports the following time bounds (n is the number of words currently in the dictionary).

Input

The first line contains an integer q: the number of operations. q lines follow.

For each of the next q lines, there is one of three possibilites.

learn xyz - Mahesh must add the word "xyz" to his dictionary. Each word has 10-letters. Words contain only lowercase english letters from 'a' to 'z'.

reportsmallest - Mahesh must report the lexicographically smallest word in his dictionary

forgetsmallest - Mahesh must forget the lexicographically smallest word in his dictionary

Output

Print nothing for the learn operation.

For the reportsmallest opearation, print the answer (lexicographically smallest word in Mahesh's dictionary).

For the forgetsmallest operation, print the word that Mahesh must forget.

Constraints

1 <= q <= 5 * 10^5

Example

Input:
10
learn hawzslzptx
learn ifvubuhzjh
learn qyxhjloxym
reportsmallest
learn agcchgaiej
reportsmallest
forgetsmallest
reportsmallest
learn ebkajcggah
reportsmallest

Output:
hawzslzptx
agcchgaiej
agcchgaiej
hawzslzptx
ebkajcggah