Bureaucracy

You have been employed as a receptionist at a particularly understaffed consultancy firm for ducks and will have to deal with $N$ events of ducks coming and going.

Each duck has a name $s_i$ and when they arrive they will be assigned a ticket number. The assigned ticket numbers are in no particular order as you simply have a large pile of unsorted tickets on your desk from which you pick a random ticket to assign to a duck. When a consultant desk becomes free, you will be asked call up the duck with number $t_i$. Occasionally, ducks will forget their number and so will ask you to remind them. Some ducks may have to visit multiple consultants, and so may be called up multiple times.

You need to implement a program to handle $N$ events of ducks arriving, getting called up, or forgetting their ticket number.

Input

The first line will contain a single integer $N$, the number of events.

The following $N$ lines will have one of three forms:

• $A \space s_i \space t_i$ meaning that you need to assign ticket $t_i$ to the duck $s_i$
• $N \space t_i$ indicating that you need to find the name of the duck who has been given ticket $t_i$
• $T \space s_i$ indicating that you need to find the ticket number assigned to duck $s_i$

Output

Output one line with a single integer per every $N$ or $T$ event.

For every event where a duck is called up you need to output the name of the duck that needs to be called. For every event where a duck forgets their ticket number you need to output their ticket number.

Constraints

• $1 \le N \le 200,000$
• $1 \le t_i \le 10^6$
• Duck names will consist of at most $16$ lower case English characters.
• No ticket will be assigned to more than one duck.
• No duck will be assigned more than one ticket.
• It is guaranteed that every type $N$ event will correspond to a ticket number that has already been assigned.
• It is guaranteed that every type $T$ event will correspond to a duck's name that has already been assigned a number.

Subtasks

• Subtask 1 (30%): $N \le 2,000$
• Subtask 2 (27%): A duck will never forget their ticket number.
• Subtask 3 (43%): No further constraints.

Sample Explanations

Sample 1

There are five events:

• albert is assigned ticket number 6
• alfred is asisgned ticket number 1
• The duck with ticket number 6 is called up. This corresponds to albert.
• andrew is assigned ticket number 3
• andrew has forgot what his number is, so comes up to ask for it. His number is 3.