JOI 君是一个生物学家。他准备对蚂蚁和方糖做一些实验。

JOI 君的实验在一个长度为 $10^9$ 的木条上进行。这根木条被从左往右放置。木条上距离左端点 $x$ 的点被称作坐标为 $x$ 的点。

现在，木条上什么都没有。JOI 君将会进行 $Q$ 次操作。第 $i$ 个操作 $(1 \le i \le Q)$ 由三个整数 $T_i,X_i,A_i$ 描述，表示：

• 若 $T_i=1$，JOI 君在坐标为 $X_i$ 的点处放了 $A_i$ 个蚂蚁。
• 若 $T_i=2$，JOI 君在坐标为 $X_i$ 的点处放了 $A_i$ 块方糖。

由于蚂蚁和方糖都很小，所以可能会有一些蚂蚁和方糖放在同一个点上。JOI 君也可能在同一个点执行多次操作。

这次实验中使用的蚂蚁具有「好奇心强」的萌点。具体地，当 JOI 君拍手时，每个蚂蚁会执行以下操作：

• 如果存在一块方糖与该蚂蚁距离不超过 $L$，它会选择任意一块并吃掉。

可能存在多个蚂蚁同时吃掉一块方糖的情况。

对于每个 $k$ $(1\le k \le Q)$，JOI 君想要知道以下问题的答案。

• 假设 JOI 君在第 $k$ 次操作后拍了一次手，最多有多少块方糖被至少一个蚂蚁吃掉了？

请写一个程序，对于给定的 JOI 君执行的操作和 $L$ 的值，对于所有 $k$ 回答 JOI 君的每个问题。

注意 JOI 君并不会真的拍手。因此蚂蚁的位置不会改变，方糖也不会被吃掉。

输入格式

第一行，两个正整数 $Q,L$，表示操作个数和蚂蚁可能吃到的方糖的范围。

接下来 $Q$ 行，其中第 $i$ $(1 \le i \le Q)$ 包含三个整数 $T_i,X_i,A_i$，表示一次操作。

输出格式

输出 $Q$ 行，第 $k$ $(1 \le k \le Q)$ 行包含一个整数，表示若 JOI 君在第 $k$ 次操作后拍了一次手，被至少一个蚂蚁吃掉的方糖的个数可能的最大值。

样例一

input

4 1
1 1 1
2 2 1
1 3 1
2 0 1

output

0
1
1
2

explanation

在这组样例中，所有操作和每个 $k$ 的答案如下：

1. JOI 君在坐标为 $1$ 的点放了一个蚂蚁。
   由于没有方糖，对应的答案为 $0$。
2. JOI 君在坐标为 $2$ 的点放了一块方糖。
   假设 JOI 君此时拍手，则坐标为 $1$ 的蚂蚁会吃掉坐标为 $2$ 的方糖，所以对应的答案为 $1$。
3. JOI 君在坐标为 $3$ 的点放了一个蚂蚁。
   假设 JOI 君此时拍手，则坐标为 $1,3$ 的蚂蚁会同时吃掉坐标为 $2$ 的方糖，所以对应的答案为 $1$。
4. JOI 君在坐标为 $0$ 的点放了一块方糖。
   假设 JOI 君此时拍手，则坐标为 $1,3$ 的蚂蚁可以分别吃掉坐标为 $0,2$ 的方糖，所以对应的答案为 $2$。

这组样例满足子任务 $1,2,4$ 的限制。

样例二

见附件下载中的 ex_sugar2.in 和 ex_sugar2.ans。

这组样例满足子任务 $1,2,4$ 的限制。

样例三

见附件下载中的 ex_sugar3.in 和 ex_sugar3.ans。

这组样例满足子任务 $1,4$ 的限制。

样例四

见附件下载中的 ex_sugar4.in 和 ex_sugar4.ans。

这组样例满足子任务 $1,3,4$ 的限制。

数据范围与提示

对于所有数据，满足：

• $1 \le Q \le 500\,000$。
• $1 \le L \le 10^9$。
• $T_i \in \{1,2\}$。
• $0 \le X_i \le 10^9$ $(1 \le i \le Q)$。
• $1 \le A_i \le 10^9$ $(1 \le i \le Q)$。

详细子任务附加限制及分值如下表所示：

时间限制：$\texttt{4s}$

空间限制：$\texttt{1GB}$