Protecting lawn

题号：NC17367
时间限制：C/C++/Rust/Pascal 4秒，其他语言8秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

Niuniu is interested in a game called Plants vs Zombies. Niuniu likes wall-nuts and spikeweeds very much. The wall-nuts have hard shells which you can use to protect other plants. Spikeweeds hurt any zombies that step on them. The game with only wall-nuts and spikeweeds work as follow:

We can represent the lawn as a straight line of length L. Your house is located at position 0. The zombies appear at position L. The lawn has L grids. The length of a grid is 1. (You can represent the i-th grid with a segment [i-1,i]) You can place plants in the grids and one grid cannot contain more than one plant. The zombies walk from right to left with a speed of 1 per second. Every zombie has HP. When HP decreases to 0, the zombie will die and disappear from the lawn. The wall-nuts can stop the zombies. The zombies will stop to eat the wall-nut when they step into the grid of the wall-nut. (the zombie will stop at position i if the wall-nut is in the i-th grid) Every wall-nut has a DUR. The wall-nuts will disappear after being eaten by at least one zombie for exactly DUR seconds. (It is not affected by the number of zombies) The spikeweed will damage the zombies in its grid with continuous damage of 1HP per second. Note that if the i-th grid is a wall-nut and the (i+1)-th grid is a spikeweed, then the zombies will be damaged by the spikeweed while they are eating the wall-nut.

Niuniu wants to do four types of queries:

1) At moment t_i, place a wall-nut with DUR_i in the p_i-th grid. It is guaranteed that the grid hasn’t been placed any plants before.

2) At moment t_i, place a spikeweed in the p_i-th grid. It is guaranteed that the grid hasn’t been placed any plants before. (The grid isn’t allowed to place a plant even though the wall-nut in the grid disappears)

3) At moment t_i, a zombie with HP_i appears at position L.

4) At moment t_i, query the position of the zombie which appeared in the x_i-th query. If the zombie has reached your house with HP strictly higher than zero, then you should print “0”. If the zombie is dead(or it dies exactly at moment t_i), then you should print the position where it died. Otherwise you should print the position of it.

Can you answer the queries?

输入描述:

The first line contains twointegers Q and L(1 ≤ Q,L ≤ 400000), which means the number of queries andthe length of the lawn.

Each of the following Q lines describes a query:

Query 1: W t_i p_i DUR_i
Query 2: S t_i p_i
Query 3: Z t_i HP_i
Query 4: Q t_i x_i
See the description of the query in the problem description.
$(1 \le t_i \le t_{i+1} \le 10^8 \quad 1 \le p_i \le L \quad 1 \le DUR_i , HP_i \le 10^8 \quad \sum{DUR_i} \le 10^8 )$

输出描述:

For each query of type 4, print one number in a single line, which is the position of the zombie.

示例1

输入

复制

输出

复制

备注:

There’re |x-y| seconds between moment x and moment y.

The zombies won’t be stopped at position i if there is a wall-nut in the (i+1)-th grid. (This happens when you place a wall-nut behind the zombie)