24950번 - Ants and Sugar 서브태스크다국어

JOI-kun is a biologist. He plans an experiment on ants and sugar.

JOI-kun’s experiment takes place on a long straight stick of length $1\,000\,000\,000$ ($= 10^9$). It is placed from the left to the right. The point on the stick which is located at a distance $x$ from the leftmost point is called the point of coordinate $x$.

Now, nothing is placed on the stick. JOI-kun will perform the $Q$ operations. The $i$-th operation ($1 ≤ i ≤ Q$) is specified by the three integers $T_i$, $X_i$, $A_i$. They mean as follows.

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

Since ants and sugar cubes are very small, it is possible to place some of them at the same point. JOI-kun may perform several operations at the same point.

The ants used in this experiment have curious properties. Precisely, if JOI-kun claps hands, every ant will do the following.

• If there is a sugar cube at a distance less than or equal to $L$ from the ant, the ant will choose any one of them and eat it.

It may happen that several ants eat the same sugar cube at the same time.

For every $k$ ($1 ≤ k ≤ Q$), JOI-kun wants to know the answer to the following question.

• Assume that JOI-kun claps hands after the $k$-th operation. What is the maximum possible number of sugar cubes eaten by at least one ant?

Write a program which, given the operations performed by JOI-kun and the value of $L$, answers to JOI-kun’s questions for all $k$.

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

Read the following data from the standard input. Given values are all integers.

$\begin{align*}& Q \, L \\ & T_1 \, X_1 \, A_1 \\ & T_2 \, X_2 \, A_2 \\ & \vdots \\ & T_Q \, X_Q \, A_Q \end{align*}$

Write $Q$ lines to the standard output. The $k$-th line ($1 ≤ k ≤ Q$) of output should contain the maximum possible number of sugar cubes eaten by at least one ant if JOI-kun claps hands after the $k$-th operation.

• $1 ≤ Q ≤ 500\,000$.
• $1 ≤ L ≤ 1\,000\,000\,000$ ($= 10^9$).
• $T_i$ is $1$ or $2$ ($1 ≤ i ≤ Q$).
• $0 ≤ X_i ≤ 1\,000\,000\,000$ ($= 10^9$) ($1 ≤ i ≤ Q$).
• $1 ≤ A_i ≤ 1\,000\,000\,000$ ($= 10^9$) ($1 ≤ i ≤ Q$).