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$

or

• $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.

7 100
1 15 60
1 25 80
2 30
1 45 0
2 60
2 70
2 80

85
100
25
-1

The seven queries are processed in the following order.

• At time $15$, a battery with charge level $60$ is plugged in. At this point, the charger has a battery with charge level $60$.
• At time $25$, a battery with charge level $80$ is plugged in. At this point, the charger has batteries with charge levels $70, 80$.
• At time $30$, the charger has batteries with charge levels $75, 85$. Of these, the battery with charge level $85$ is unplugged.
• At time $45$, a battery with charge level $0$ is plugged in. At this point, the charger has batteries with charge levels $0, 90$.
• At time $60$, the charger has batteries with charge levels $15, 100$. Of these, the battery with charge level $100$ is unplugged.
• At time $70$, the charger has a battery with charge level $25$. This battery, with charge level $25$, is unplugged.
• At time $80$, no battery is plugged into the charger. Thus, no battery is unplugged.

20 380736236
1 21873985 256702097
2 86369729
1 114301317 288304981
1 147244640 305840435
2 150951976
1 331581391 50335458
1 352989552 47577202
1 400130024 345362760
2 458793150
2 509082216
1 591375600 197371572
1 617022014 101276068
1 679649471 310249627
1 796351653 268586022
1 825648347 129608152
2 908069704
2 921770319
1 949684819 372272469
1 971850999 335461408
2 986253026

321197841
324955640
380736236
380736236
380736236
380736236
380736236

• 来源：AtCoder ABC 471 D