Problem B
Doctor Kattis

It is common for cats to have puncture wounds with different severity of infections. To help her local neighbourhood, Doctor Kattis decided to open a clinic! However, there are too many injured cats that come so she needs to prioritise her patients.

Given the names of $\textbf{N}$ injured cats, their level of severity, and subsequent updates of their infection level, determine which cat Doctor Kattis needs to give her most attention to.

A cat with higher infection level has higher priority. If there are more than one cat with the same infection level, Doctor Kattis will give priority to the cat who arrived at the clinic first.

There will be $4$ types of commands:

1. ArriveAtClinic(catName, infectionLevel): This will be indicated by a starting integer $0$ followed by catName and infectionLevel, e.g. $0$ LUNA $31$. catName is a String that is all UPPERCASE with length $1$ to $15$ characters. The cat names are all unique. infectionLevel is an integer $(30 \le $ infectionLevel $ \le 100)$.

2. UpdateInfectionLevel(catName, increaseInfection): This will be indicated by a starting integer $1$ followed by catName and increaseInfection, e.g. $1$ LUNA $24$. catName is guaranteed to have already arrived at clinic. increaseInfection is an integer $(0 \le $ increaseInfection $\le 70)$. The infection level has a maximum value of $100$ and the update infection commands are given in such a way that the overall infection level of any cat will not exceed $100$.

3. Treated(catName): This will be indicated by a starting integer $2$ followed by catName, e.g. $2$ KITTY. catName is guaranteed to have already arrived at the clinic. catName leaves the clinic after being treated.

4. Query(): This will be indicated by a single integer $3$. Your job is to print the catName with the highest infection level or “The clinic is empty” if there are no more cats.

Input

The first line of input contains an integer $N$, denoting the number of commands $(1 \le N \le 1\, 000\, 000)$. There will be up to $200\, 000$ cats. This will be followed by $N$ commands as described above.

Output

Each time the Query() command is encountered, the catName with highest infection level or “The clinic is empty” is to be printed in one line.

Subtasks

1. $\textbf{(30 points)}$: $1 \le N \le 100$, there will be up to $15$ cats

2. $\textbf{(30 points)}$: $1 \le N \le 1\, 000\, 000$, there will be up to $200\, 000$ cats. However, there is no call to UpdateInfectionLevel command and the cat with the highest infection level is always the first to be be treated, i.e. you can see this as Treated(Query())

3. $\textbf{(40 points)}$: $1 \le N \le 1\, 000\, 000$, there will be up to $200\, 000$ cats. However, there will be frequent UpdateInfectionLevel commands and the cat with the highest infection level is not always the first to be treated

Explanation

In the sample test case, we have $N = 15$ commands:

1. ArriveAtClinic(“LUNA”, $31$)

2. ArriveAtClinic(“NALA”, $55$)

3. ArriveAtClinic(“BELLA”, $42$)

4. Query(). You have to print out “NALA”, as she is currently the one with the highest infection level. To be precise, at the moment the order is: (NALA, $55$), (BELLA, $42$), (LUNA, $31$).

5. ArriveAtClinic(“KITTY”, $77$)

6. Query(). Now you have to print out “KITTY”. The current order is: (KITTY, $77$), (NALA, $55$), (BELLA, $42$), (LUNA, $31$).

7. UpdateInfectionLevel(“LUNA”, $24$). After this event, the one with the highest infection level is still KITTY with infectionLevel = $77$. “LUNA” now has infection level = $31+24$ = $55$, but this is still $22$ smaller than “KITTY”. Note that “NALA” also has infection level = $55$ but “LUNA” is in front of “NALA” because “LUNA” arrived at the clinic earlier. The current order is: (KITTY, $77$), (LUNA, $55$), (NALA, $55$), (BELLA, $42$).

8. Treated(“KITTY”). “KITTY” now has been treated ‘instantly’, and “KITTY” leaves Doctor Kattis’s clinic.

9. Query(). Now you have to print out “LUNA”, as the current order is: (LUNA, $55$), (NALA, $55$), (BELLA, $42$).

10. Treated(“BELLA”). “BELLA” leaves Doctor Kattis’s clinic.

11. Query(). The answer is still: “LUNA”. The current order is: (LUNA, $55$), (NALA, $55$).

12. Treated(“LUNA”). “LUNA” leaves Doctor Kattis’s clinic.

13. Query(). You have to answer: “NALA”. The current order is: (NALA, $55$).

14. Treated(“NALA”). “NALA” leaves Doctor Kattis’s clinic.

15. Query(). You have to answer: “The clinic is empty”.

15
0 LUNA 31
0 NALA 55
0 BELLA 42
3
0 KITTY 77
3
1 LUNA 24
2 KITTY
3
2 BELLA
3
2 LUNA
3
2 NALA
3

NALA
KITTY
LUNA
LUNA
NALA
The clinic is empty