IITKESO207PA3Q2 - Memory Game 2

After succesfully completing the challenge given to him in Memory Game 1, Mahesh has now challenged Nitish to a different memory game. Mahesh will ask Nitish to learn words and then perform certain operations on them. The operations are as follows:

1) learn xyz: This command tells Nitish to add the word "xyz" to his dictionary.

2) forget xyz: This command tells Nitish to forget "xyz" from the dictionary. It is guaranteed that word that is asked to be forgotten will be present in the dictionary.

3) findrank xyz: Find the rank of the word "xyz" if the words are arranged in lexicographic order. The lexicographically smallest word is given rank 1.

Nitish needs your help in order to complete the challenge. You are required to design a suitable data structure that supports the given operations in an efficient manner.

Important point: A word is simply a string of lowecase characters (a to z). Moreover, it is guaranteed that each word has exactly 10 characters.

Input

The first line contains an integer q denoting the number of queries. q lines follow.

Each of the next line contains one of the 3 different queries

learn xyz - Add xyz to dictionary.

forget xyz - Remove xyz from dictionary.

findrank xyz - Find rank of xyz in the dictionary.

Output

Print nothing in case of learn operation.

For forget operation, print the rank of the word that is removed.

For findrank operation, print the rank of the word.

Constraints

1 <= q <= 5 * 10^5

Example

Input:
10
learn monhdjaecg
learn
aelakggcfe
aelakggcfe learn mhbmldlcim
learn ahlidlmdlj
learn dlneeklean
forget mhbmldlcim
findrank ahlidlmdlj
findrank monhdjaecg
forget ahlidlmdlj
findrank monhdjaecg
Output:
4
2
4
2
3

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

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.