题目描述

有一个充电器，它拥有无限多个充电插槽。在时刻 $0$，所有插槽都是空的。

电池的最大容量为 $V$。当一块电池插在插槽中时，它会以 $1$ 的速率充电，直到电量达到最大容量（也就是说，每经过 $1$ 单位时间，电量增加 $1$）。

按顺序处理 $Q$ 个询问。第 $q$ 个询问以下列格式之一给出。在此保证 $t_1 < \dots < t_Q$。

• 类型 $1$（$1\ t_q\ w_q$）：在时刻 $t_q$，把一块电量为 $w_q$ 的电池插入一个插槽。
• 类型 $2$（$2\ t_q$）：在时刻 $t_q$，从插槽中拔出一块电量最高的电池，并输出该电池的电量。如果所有插槽中都没有电池，则输出 $-1$。

数据范围

• $1 \leq Q \leq 3 \times 10^5$
• $1 \leq V \leq 10^9$
• 对于类型 $1$ 的询问，$1 \leq t_q \leq 10^9$。
• 对于类型 $1$ 的询问，$0 \leq w_q \leq V$。
• 对于类型 $2$ 的询问，$1 \leq t_q \leq 10^9$。
• $t_1 < \dots < t_Q$
• 输入中的所有值均为整数。

输入格式

输入从标准输入读入，格式如下：

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

其中 $\mathrm{query}_q$ 表示第 $q$ 个询问，以下列两种格式之一给出：

• $1$ $t_q$ $w_q$

或

• $2$ $t_q$

输出格式

设类型 $2$ 的询问共有 $x$ 个。输出 $x$ 行。

第 $k$ 行（$1 \leq k \leq x$）应包含第 $k$ 个类型 $2$ 询问需要输出的值。

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

85
100
25
-1

这七个询问按如下顺序处理。

• 在时刻 $15$，插入一块电量为 $60$ 的电池。此时充电器中有一块电量为 $60$ 的电池。
• 在时刻 $25$，插入一块电量为 $80$ 的电池。此时充电器中有电量分别为 $70, 80$ 的电池。
• 在时刻 $30$，充电器中有电量分别为 $75, 85$ 的电池。其中电量为 $85$ 的电池被拔出。
• 在时刻 $45$，插入一块电量为 $0$ 的电池。此时充电器中有电量分别为 $0, 90$ 的电池。
• 在时刻 $60$，充电器中有电量分别为 $15, 100$ 的电池。其中电量为 $100$ 的电池被拔出。
• 在时刻 $70$，充电器中有一块电量为 $25$ 的电池。这块电量为 $25$ 的电池被拔出。
• 在时刻 $80$，充电器中没有插任何电池。因此没有电池被拔出。

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

子任务设置

• 子任务 1（120 分）：$Q \le 2000$。
• 子任务 2（280 分）：无特殊限制。