JOI-kun 是一位生物学家，他正在计划一项关于蚂蚁和糖的实验。
JOI-kun 的实验是在一根长度为 $1\,000\,000\,000$ ($= 10^9$) 的长直木棍上进行的。木棍从左到右放置。木棍上距离最左端距离为 $x$ 的点被称为坐标为 $x$ 的点。
现在，木棍上什么都没有。JOI-kun 将执行 $Q$ 次操作。第 $i$ 次操作 ($1 \le i \le Q$) 由三个整数 $T_i, X_i, A_i$ 指定，含义如下：
- 如果 $T_i = 1$，JOI-kun 在坐标为 $X_i$ 的点放置 $A_i$ 只蚂蚁。
- 如果 $T_i = 2$，JOI-kun 在坐标为 $X_i$ 的点放置 $A_i$ 块方糖。
由于蚂蚁和方糖非常小，可以将它们放置在同一个点上。JOI-kun 可以在同一个点执行多次操作。
实验中使用的蚂蚁具有奇特的特性。具体来说，如果 JOI-kun 拍手，每只蚂蚁都会执行以下操作：
- 如果蚂蚁距离内（距离小于或等于 $L$）有方糖，蚂蚁会从中选择任意一块并吃掉它。
可能会有多只蚂蚁同时吃掉同一块方糖。
对于每个 $k$ ($1 \le k \le Q$)，JOI-kun 想知道以下问题的答案：
- 假设 JOI-kun 在第 $k$ 次操作后拍手。至少有一只蚂蚁吃掉的方糖数量的最大可能值是多少？
请编写一个程序，给定 JOI-kun 执行的操作和 $L$ 的值，回答 JOI-kun 对所有 $k$ 的提问。
注意，JOI-kun 实际上并没有拍手。因此，蚂蚁的位置不会改变，方糖也不会被吃掉。
输入格式
从标准输入读取以下数据。给定值均为整数。
$Q \ L$ $T_1 \ X_1 \ A_1$ $T_2 \ X_2 \ A_2$ $\vdots$ $T_Q \ X_Q \ A_Q$
输出格式
向标准输出写入 $Q$ 行。第 $k$ 行 ($1 \le k \le Q$) 应包含如果 JOI-kun 在第 $k$ 次操作后拍手，至少有一只蚂蚁吃掉的方糖数量的最大可能值。
数据范围
- $1 \le Q \le 500\,000$
- $1 \le L \le 1\,000\,000\,000$ ($= 10^9$)
- $T_i$ 为 $1$ 或 $2$ ($1 \le i \le Q$)
- $0 \le X_i \le 1\,000\,000\,000$ ($= 10^9$) ($1 \le i \le Q$)
- $1 \le A_i \le 1\,000\,000\,000$ ($= 10^9$) ($1 \le i \le Q$)
子任务
- (6 分) $Q \le 3\,000$
- (16 分) $L = 1, X_i \le Q - 1, X_i + T_i$ 为偶数 ($1 \le i \le Q$)
- (26 分) $Q$ 为偶数，$T_i = 1$ ($1 \le i \le Q/2$), $T_i = 2$ ($Q/2 + 1 \le i \le Q$)
- (52 分) 无附加限制
样例
样例输入 1
4 1 1 1 1 2 2 1 1 3 1 2 0 1
样例输出 1
0 1 1 2
说明
在该样例输入中，操作及对每个 $k$ 的问题回答如下：
- JOI-kun 在坐标 1 处放置了一只蚂蚁。 假设 JOI-kun 拍手。由于没有方糖，对于 $k=1$ 的问题答案为 0。
- JOI-kun 在坐标 2 处放置了一块方糖。 假设 JOI-kun 拍手。此时，坐标 1 处的蚂蚁吃掉了坐标 2 处的方糖。因此，对于 $k=2$ 的问题答案为 1。
- JOI-kun 在坐标 3 处放置了一只蚂蚁。 假设 JOI-kun 拍手。此时，坐标 1 和坐标 3 处的蚂蚁都吃掉了坐标 2 处的方糖。因此，对于 $k=3$ 的问题答案为 1。
- JOI-kun 在坐标 0 处放置了一块方糖。 假设 JOI-kun 拍手。如果坐标 1 处的蚂蚁吃掉坐标 0 处的方糖，且坐标 3 处的蚂蚁吃掉坐标 2 处的方糖，则被至少一只蚂蚁吃掉的方糖数量达到最大。因此，对于 $k=4$ 的问题答案为 2。
该样例输入满足子任务 1、2、4 的限制。