Description

An amusement park has started operating a brand new simulated roller coaster. The simulated track consists of $n$ rail segments, and the first and last segments are connected to form a loop. The first rail segment starts at height $0$.

The operator Byteman can modify the track by adjusting the heights of several consecutive rail segments. The heights of the segments before the modified part are not affected. Each time the rail heights are adjusted, the segments after the modified part must be raised or lowered to keep the track connected, and the starting height must remain $0$. The next page illustrates the modification process.

At the start of each run, the car has enough energy to reach height $h$. That is, as long as the height of the track does not exceed $h$, the car keeps moving, even until it finishes.

Given the daily runs and modifications, for each run compute how many rail segments the car passes before it stops.

The rails are represented as a sequence of $n$ numbers, where each number corresponds to one rail segment. The $i$-th value $d_i$ denotes the height change on the $i$-th segment. In other words, if the car’s height is $h$ before reaching segment $i$, then after passing segment $i$, the height becomes $h+d_i$.

Initially, the track is a horizontal line, meaning $d_i=0$ for all $i$. Runs and modifications are interleaved. Each modification is given by three numbers: $a$, $b$, and $D$, meaning that all $d_i$ for $i$ from $a$ to $b$ (inclusive) are set to $d_i=D$. Each run is given a number $h$, the maximum height the car can reach.

Input Format

The first line of input contains a positive integer $n$, the number of rail segments.

The following lines contain modifications and runs, each starting with an identifier:

• Modification: a letter I, followed by integers $a$, $b$, and $D$, separated by single spaces.
• Run: a letter Q, followed by an integer $h$, separated by a single space.
• A letter E: the termination symbol, indicating the end of input.

You may assume that at any time, the height of any rail segment is within the range $[1,1000000000]$.

The input contains no more than $10000$ lines.

Output Format

For the $i$-th run, output one integer per line: the number of rail segments passed in that run.

4
Q 1
I 1 4 2
Q 3
Q 1
I 2 2 -1
Q 3
E

4
1
0
3

Hint

For $50\%$ of the testdata, $1 \le n \le 2 \times 10^4$, and the input contains no more than $1000$ lines.

For $100\%$ of the testdata, $1 \le n \le 10^9$, $1 \le a,b \le n$, $- 10^9 \le D \le 10^9$, $0 \le h \le 10^9$.

Translated by ChatGPT 5