Description

We all know that elephants have incredible memory, as each one has a name and a lucky number.

elfnt can remember up to $n$ friends, storing them in his memory list.
There are $q$ queries, each belonging to one of the following types:

• ASK name: Check if elfnt remembers an elephant with the given name.

  • If found in memory, print its lucky number and refresh the impression of it by moving it to the front of the list.
  • Otherwise, print "Who?".

• ADD name num: Introduce a new elephant with name and lucky number num.

  • Otherwise, add it to the front of the list.
  • If memory is full, remove the least recently used (ask or add) elephant before adding the new one.

It is guaranteed that NO same name will be added more than once using the ADD operation.

Input

The first line contains two integers $n$ and $q$, representing the size of the memory list and the query times.

The following $q$ lines, each contains a type of operation. The format are as follow.

• ADD name num
• ASK name

Constraints

• $1 \leq n \leq 5000$
• $1 \leq q \leq 2 \times 10^5$
• $1 \leq |$ name $| \leq 100$
• $1 \leq $ num $\leq 10^9$
• The name only contains lowercase letters.

Subtask

1. (Testcases 1-3) $1 \leq n, q \leq 1000$
2. (Testcases 4-8) At most $2000$ ASK queries.
3. (Testcases 9-10) No additional constraints.

Output

For each ASK query:

• Print the lucky number if name is found in memory.
• Otherwise, print "Who?".

Each output should be followed by a newline.

Sample Input  Download

Sample Output  Download

Tags

Discuss