IITKESO207PA3Q1 - Memory Game 1

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

Added by:Programming Club, IITK
Date:2018-02-03
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

hide comments
2018-02-05 19:04:15 Programming Club, IITK
@ymahajan98: Yes
2018-02-05 14:24:22
Am I allowed to use vectors for this question?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.