题目描述

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

电池的最大容量为 $V$。电池插在插口上时，会以速度 $1$ 充电，直到电量达到最大容量为止（即每经过 $1$ 单位时间，电量增加 $1$；到达 $V$ 后不再增加）。

请按顺序处理 $Q$ 个询问。题目保证 $t_1 < t_2 < \cdots < t_Q$。

• 类型 $1$（1 t w）：在时刻 $t$ 把一块电量为 $w$ 的电池插到插口上。
• 类型 $2$（2 t）：在时刻 $t$ 把当前电量最多的那块电池拔下来，并输出它的电量；若此时没有任何电池在充电，则输出 -1。

输入格式

Q V
query_1
...
query_Q

其中每个询问是下面两种格式之一：

1 t w

2 t

输出格式

设类型 $2$ 的询问共有 $x$ 个，则输出 $x$ 行，第 $k$ 行是第 $k$ 个类型 $2$ 询问的答案。

输入示例 1

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

输出示例 1

85
100
25
-1

示例 1 说明

• 时刻 $15$ 插入电量 $60$ 的电池；
• 时刻 $25$ 插入电量 $80$ 的电池，此时充电器里是电量 $70$、$80$ 的两块；
• 时刻 $30$ 时两块分别是 $75$、$85$，拔掉电量 $85$ 的那块；
• 时刻 $45$ 插入电量 $0$ 的电池，此时是 $0$、$90$；
• 时刻 $60$ 时是 $15$、$100$（注意后者已经充满，被 $V = 100$ 卡住不再增加），拔掉 $100$；
• 时刻 $70$ 时只剩电量 $25$ 的一块，拔掉它；
• 时刻 $80$ 时充电器是空的，输出 -1。

输入示例 2

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

输出示例 2

321197841
324955640
380736236
380736236
380736236
380736236
380736236

示例 2 说明

时间跨度很大，后面的电池早已充满，所以连续输出了多个等于 $V = 380736236$ 的答案。

约束条件

• $1 \le Q \le 3 \times 10^5$
• $1 \le V \le 10^9$
• 类型 $1$ 的询问中 $1 \le t \le 10^9$，$0 \le w \le V$
• 类型 $2$ 的询问中 $1 \le t \le 10^9$
• $t_1 < t_2 < \cdots < t_Q$
• 所有输入值均为整数