OpenKattis
National University of Singapore

Air Rally

Baxter and Forthington are playing badminton the only correct way—ten thousand feet in the air!

They intend to rally the shuttlecock back and forth while cruising side-by-side at a constant speed. For simplicity, assume that they cruise at one distance unit per second.

Forthington hits the shuttlecock first; then, it alternates between the two of them. The rally ends when they have cruised $M$ distance units (that is, once $M$ or more distance units have been traveled, whoever is supposed to continue the rally when the shuttlecock arrives will catch it instead of hitting it back.)

Every time Baxter hits the shuttlecock, it will remain in the air for $S_1$ seconds; when Forthington returns it, the shuttlecock will remain in the air for $S_2$ seconds.

This would be simple enough, but today’s weather forecast predicts that the sky may become very cloudy. Clouds obscure vision and make hitting the shuttlecock difficult; when there is a cloud of haziness $h$ in Baxter or Forthington’s position at the time she or he hits the shuttlecock, the shuttlecock will be hit harder and remain in the air for $h$ more seconds than usual.

There are $Q$ weather updates today. In the $i^\text {th}$ update, either:

  • a cloud with haziness $H_ i$ appears at position $P_ i$ distance units from the start, or

  • the cloud at position $P_ i$ distance units from the start disappears.

After each weather update, please determine how long—in terms of the number of hits—the rally will last.

Interaction

First, your program should read four integers $Q$ ($1 \leq Q \leq 70\, 000$), $M$, $S_1$ and $S_2$ ($1 \leq M, S_1, S_2 \leq 10^{18}$), the number of weather updates, the length they will cruise in distance units, and the number of seconds the shuttlecock stays in the air when Baxter and Forthington hit it, respectively.

Then, we repeat the following process $Q$ times:

  • Your program should read the weather update. Each weather update begins with a single integer.

    • If this integer is $1$, two integers $P_ i$ ($0 \leq P_ i < M$) and $H_ i$ ($1 \leq H_ i \leq 10^{18}$) follow, denoting that a new cloud with haziness $H_ i$ appears at position $P_ i$ distance units from the start. It is guaranteed that there is not already a cloud at position $P_ i$ at the time of this query.

    • If this integer is $2$, a single integer $P_ i$ follows, denoting that the cloud at position $P_ i$ distance units from the start disappears. It is guaranteed that there is really a cloud at position $P_ i$ at the time of this query.

  • Your program writes a single line to the standard output containing a single integer, the number of hits the rally will last.

Note in particular that your program will not be provided the next weather update until you have provided the response for the current situation.

After you have provided all $Q$ responses, your answer will be checked. Your program should terminate immediately after this.

After giving each response, do not forget to output end of line and flush the output. To do this, use:

  • fflush(stdout) or cout.flush() in C++;

  • System.out.flush() in Java;

  • stdout.flush() in Python;

  • see documentation for other languages.

Sample interaction

Your output (standard output)

Kattis’ answer (standard input)

Interpretation

 

$\texttt{5 15 2 3}$

There will be $Q = 5$ weather updates. They will cruise $M = 15$ distance units; the shuttlecock stays in the air for $S_1 = 2$ seconds when Baxter hits it and $S_2 = 3$ seconds when Forthington hits it.

 

$\texttt{1 10 2}$

The first weather update creates a cloud with haziness $H_1 = 2$ at $P_1 = 10$ distance units from the start.

$\texttt{5}$

 

The shuttlecock will be hit at $0$, $3$, $5$, $8$ and $10$ distance units from the start. The rally ends when the shuttlecock is caught by Baxter at $15$ distance units from the start.

 

$\texttt{1 8 1}$

The second weather update creates a cloud with haziness $H_2 = 1$ at $P_2 = 8$ distance units from the start.

$\texttt{6}$

 

The shuttlecock will be hit at $0$, $3$, $5$, $8$, $11$ and $14$ distance units from the start. The rally ends when the shuttlecock is caught by Forthington at $16$ distance units from the start.

 

$\texttt{1 3 1}$

The third weather update creates a cloud with haziness $H_3 = 1$ at $P_3 = 3$ distance units from the start.

$\texttt{6}$

 

The shuttlecock will be hit at $0$, $3$, $6$, $9$, $11$ and $14$ distance units from the start. The rally ends when the shuttlecock is caught by Forthington at $16$ distance units from the start.

 

$\texttt{1 5 100}$

The fourth weather update creates a cloud with haziness $H_4 = 100$ at $P_4 = 5$ distance units from the start.

$\texttt{6}$

 

The new cloud does not affect the rally. The scenario is the same as before.

 

$\texttt{2 3}$

The fifth weather update removes the cloud at $P_5 = 3$ distance units from the start.

$\texttt{3}$

 

The shuttlecock will be hit at $0$, $3$ and $5$ distance units from the start. The rally ends when the shuttlecock is caught by Baxter at $108$ distance units from the start.