Problem Description

JOI-kun is a biologist. He is preparing to conduct some experiments on ants and sugars.

JOI-kun's experiment is conducted on a wooden plank of length $10^9$. This plank is placed from left to right. The point on the plank that is $x$ units away from the left endpoint is referred to as the point with coordinate $x$.

Currently, the plank is empty. JOI-kun will perform $Q$ operations. The $i$-th operation $(1 \le i \le Q)$ is described by three integers $T_i, X_i, A_i$, which indicate:

• If $T_i = 1$, JOI-kun places $A_i$ ants at the point with coordinate $X_i$.
• If $T_i = 2$, JOI-kun places $A_i$ sugar cubes at the point with coordinate $X_i$.

Since ants and sugar cubes are very small, some ants and sugar cubes may be placed at the same point. JOI-kun may also perform multiple operations at the same point.

The ants used in this experiment have a trait of being "curious." Specifically, when JOI-kun claps, each ant will perform the following action:

• If there is a sugar cube within a distance of $L$ from the ant, it will choose one and eat it.

It is possible for multiple ants to eat the same sugar cube simultaneously.

For each $k$ $(1 \le k \le Q)$, JOI-kun wants to know the answer to the following question:

• Suppose JOI-kun claps after the $k$-th operation, what is the maximum number of sugar cubes that could be eaten by at least one ant?

Please write a program that, given the operations performed by JOI-kun and the value of $L$, answers JOI-kun's questions for all $k$.

Note that JOI-kun does not actually clap. Therefore, the positions of the ants do not change, and the sugar cubes are not eaten.

Input Format

The first line contains two positive integers $Q$ and $L$, representing the number of operations and the range within which ants can eat sugar cubes, respectively.

The next $Q$ lines, where the $i$-th line $(1 \le i \le Q)$ contains three integers $T_i, X_i, A_i$, describing an operation.

Output Format

Output $Q$ lines, where the $k$-th line $(1 \le k \le Q)$ contains a single integer, representing the maximum number of sugar cubes that could be eaten by at least one ant if JOI-kun claps after the $k$-th operation.

Sample Input and Output

Sample Input #1

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

Sample Output #1

0
1
1
2

Sample Input #2

20 1
2 16 778913911
1 7 558407445
1 1 589762439
1 17 74646747
1 1 149104909
1 15 956697952
2 6 389372991
2 4 867453845
1 15 157353445
1 9 846177695
1 7 747107163
2 10 525670462
2 16 478912944
2 6 301733761
2 12 132966485
1 1 748012313
2 10 830922632
1 19 969484637
1 13 370330582
1 1 464798040

Sample Output #2

0
0
0
74646747
74646747
778913911
1168286902
1168286902
1168286902
1168286902
1168286902
1693957364
2103741597
2405475358
2405475358
2405475358
2725982591
2725982591
2858949076
2858949076

Sample Input #3

20 6
2 27 12
2 9 11
1 36 10
2 39 4
2 14 9
2 33 7
2 38 20
2 0 20
2 25 16
1 14 3
1 13 19
2 6 4
2 15 6
2 33 4
1 12 11
1 44 1
2 17 14
2 12 19
1 48 18
2 30 16

Sample Output #3

0
0
0
4
4
10
10
10
10
13
30
30
32
32
40
41
44
44
44
44

Sample Input #4

20 268886972
1 984472666 733463744
1 478477245 94817772
1 242536956 330762563
1 65794782 319137646
1 320548477 937296140
1 815011370 938193848
1 565184190 917533785
1 245417414 534089975
1 529908772 977043962
1 603891865 700935654
2 167042244 479827216
2 173921297 798343455
2 916159596 810126726
2 999299355 465535307
2 965968070 501768990
2 936073643 174976034
2 832859952 778072072
2 955489596 704853861
2 246733786 382428992
2 227669861 390905006

Sample Output #4

0
0
0
0
0
0
0
0
0
0
479827216
1278170671
2088297397
2553832704
2949828263
2949828263
3727900335
3727900335
4110329327
4501234333

Notes

[Sample Explanation #1]

In this sample, all operations and the answers for each $k$ are as follows:

1. JOI-kun places one ant at the point with coordinate $1$.
   Since there are no sugar cubes, the answer is $0$.
2. JOI-kun places one sugar cube at the point with coordinate $2$.
   If JOI-kun claps now, the ant at coordinate $1$ will eat the sugar cube at coordinate $2$, so the answer is $1$.
3. JOI-kun places one ant at the point with coordinate $3$.
   If JOI-kun claps now, the ants at coordinates $1$ and $3$ will both eat the sugar cube at coordinate $2$, so the answer is $1$.
4. JOI-kun places one sugar cube at the point with coordinate $0$.
   If JOI-kun claps now, the ants at coordinates $1$ and $3$ can each eat the sugar cubes at coordinates $0$ and $2$, so the answer is $2$.

This sample satisfies the constraints of subtasks $1, 2, 4$.

[Sample Explanation #2]

This sample satisfies the constraints of subtasks $1, 2, 4$.

[Sample Explanation #3]

This sample satisfies the constraints of subtasks $1, 4$.

[Sample Explanation #4]

This sample satisfies the constraints of subtasks $1, 3, 4$.

[Data Range]

For all data, the following constraints apply:

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

Detailed subtask additional constraints and scores are as follows:

见题面 Input 部分

见题面 Output 部分