Problem B
Clinic

You work at a clinic. The clinic factors in the waiting time when selecting patients to treat next. This approach was adopted to prevent patients from having to wait too long before being treated. Your task is to help the clinic perform $3$ types of queries:

1. Process a patient arrival to the clinic. The patient will have an arrival time $T$, a name $M$, and a severity $S$ that is accessed automatically by scanners at the entrance.

2. At time $T$, the doctor is ready to treat a patient. Every time this happens, the clinic will calculate priority values for every patient waiting in the clinic, and the patient with the highest priority value will be treated first. The priority value is computed as the following sum

   \[ S + K \cdot W \]

   where $S$ is the severity value of the patient, $K$ is the constant that the clinic uses, and $W$ is the total time the patient has been waiting in the clinic. If there are multiple patients with that value, the patient with the lexicographically smallest name is treated next. Your program will announce the name of that patient.

3. At time $T$, the clinic receives a notification stating that, due to unfortunate circumstances, a patient with name $M$ has left the queue permanently. If no patient with name $M$ exists in the queue, it is always a false alarm and will be ignored by the clinic. Otherwise, the notification is guaranteed to be valid and should be processed accordingly.

Input

The first line of the input contains $2$ integers, $1 \leq N \leq 200\, 000$, the number of queries to be processed, and $0 \leq K \leq 10\, 000\, 000$, the constant for the clinic. $N$ lines follow, each line beginning with an integer $Q$ where $Q$ = $1$, $2$ or $3$. $Q = 1$ denotes a query of the first type and will be followed by an integer $T$, a string $M$ and an integer $S$. $Q = 2$ denotes a query of the second type and will be followed by an integer $T$. $Q = 3$ denotes a query of the third type and will be followed by an integer $T$ and a string $M$. For all queries, $0 \leq T,S \leq 10\, 000\, 000$, and $T$ values are strictly increasing. $M$ is a non-empty alphanumeric string containing no spaces, and contains at most $10$ characters. All patients have unique names. There is at least one query of the second type.

Output

For each query of the second type, output the name of the patient who will be treated on a new line. If the clinic is empty, print the string “doctor takes a break” (without quotes) on a new line instead.

Subtasks

1. (28 Points): $1 \leq N \leq 10,000$. There is no query of type $3$. You can assume that $K = 0$.

2. (32 Points): $1 \leq N \leq 10,000$. There is no query of type $3$.

3. (20 Points): There is no query of type $3$.

4. (20 Points): No additional constraints.

Warning

The I/O files are large. Please use fast I/O methods.

5 1
1 10 Alice 5
1 15 Bob 15
2 20
2 25
2 30

Bob
Alice
doctor takes a break

5 5
1 10 Alice 5
1 15 Bob 15
2 20
2 25
2 30

Alice
Bob
doctor takes a break