Mountains

A new roller-coaster simulator has been installed at an amusement park. The simulated track is a sequence of $n$ rails joined end to end, with the start of the first rail fixed at elevation $0$.

The simulator stores the track as a sequence of $n$ elevation changes $d_1, d_2, \dots, d_n$. Here $d_i$ is the elevation change (in centimetres) over the $i$-th rail: if a car is at elevation $e$ after traversing $i-1$ rails, then after traversing the $i$-th rail it is at elevation $e + d_i$. Thus the start is at elevation $0$, and the elevation after $i$ rails is $d_1 + d_2 + \dots + d_i$.

Initially every rail is horizontal; that is, $d_i = 0$ for all $i$.

Throughout the day two kinds of events are interleaved.

• Reconfiguration: given three integers $a$, $b$, and $D$. For every rail $i$ with $a \le i \le b$, the elevation change is set to $d_i = D$. The elevation change over every other rail is unchanged. The start stays at elevation $0$, and the rest of the track is shifted up or down as needed so that it remains connected.
• Ride: given one integer $h$. A car is launched with just enough energy to reach height $h$. The car keeps moving as long as the elevation of the track does not exceed $h$ and the end of the track has not been reached.

For each ride, determine the number of rails the car fully traverses before it stops.

The first line contains the number of rails $n$ ($1 \le n \le 10^9$).

The following lines contain reconfigurations and rides interleaved, followed by an end marker. Each line is one of:

• Reconfiguration: the letter I and three integers $a$, $b$, $D$ separated by single spaces ($1 \le a \le b \le n$, $-10^9 \le D \le 10^9$). It sets $d_i = D$ for every rail $a \le i \le b$.
• Ride: the letter Q and an integer $h$ separated by a single space ($0 \le h \le 10^9$).
• A single letter E: the end marker denoting the end of the input.

You may assume that at any moment the elevation of every point on the track lies in the interval $[0, 10^9]$ centimetres. The input contains at most $100\,000$ lines.

In $50\%$ of the test cases, $n$ satisfies $1 \le n \le 20\,000$ and there are at most $1\,000$ lines of input.

For each ride, print on its own line a single integer — the number of rails the car traverses. The $i$-th line corresponds to the $i$-th ride.

The track before and after each reconfiguration. The x axis denotes the rail number; the y axis and the numbers above points denote elevation; the numbers above segments denote elevation changes.