Problem Statement

There is a charger with an unlimited number of charging slots. At time $0$, all slots are empty.

The maximum capacity of a battery is $V$. While a battery is plugged into a slot, it is charged at a rate of $1$ until its charge level reaches the maximum capacity (that is, the charge level increases by $1$ for every $1$ unit of time that passes).

Process $Q$ queries in order. The $q$-th query is given in one of the following formats. Here, it is guaranteed that $t_1 < \dots < t_Q$.

• Type $1$ ($1\ t_q\ w_q$): At time $t_q$, plug one battery with charge level $w_q$ into a slot.
• Type $2$ ($2\ t_q$): At time $t_q$, unplug one battery with the highest charge level from its slot, and output that battery's charge level. If there is no battery plugged into any slot, output $-1$ instead.

Constraints

• $1 \leq Q \leq 3 \times 10^5$
• $1 \leq V \leq 10^9$
• For type $1$ queries, $1 \leq t_q \leq 10^9$.
• For type $1$ queries, $0 \leq w_q \leq V$.
• For type $2$ queries, $1 \leq t_q \leq 10^9$.
• $t_1 < \dots < t_Q$
• The input values are all integers.

Input

The input is given from Standard Input in the following format:

Q V
\mathrm{query}_1
\vdots
\mathrm{query}_Q

Here, $\mathrm{query}_q$ represents the $q$-th query, and is given in one of the following two formats:

1 t_q w_q

2 t_q

Output

Let $x$ be the number of type $2$ queries. Output $x$ lines.

The $k$-th line ($1 \leq k \leq x$) should contain the value to be outputed for the $k$-th type $2$ query.