Mountains
In the amusement park "Oh-oh-oh", a new roller coaster attraction has been introduced. The track is composed of n rails connected in sequence. The starting point of the first rail is at a height of 0. Operator Petya can adjust the attraction by altering the incline of several consecutive rails as he chooses. The inclines of all other rails remain unchanged. When a rail configuration is modified, the positions of the subsequent rails are adjusted to ensure the track stays connected.
Each cart launch is powered with enough energy to reach a height of h. This means the cart will continue moving until it surpasses the height h or reaches the end of the track.
For each launch, determine how many rails the cart will traverse before stopping, based on the history of all rail configuration changes and launch times.
The track can be visualized as a sequence of n inclines d_i, one for each rail. Initially, all rails are horizontal, so d_i = 0 for all i.
Each configuration change is specified by the numbers a, b, and D: all rails from the a-th to the b-th inclusive will have an incline of D after this change.
Each cart launch is defined by a single integer h - the maximum height the cart can achieve.
Input
The first line contains an integer n (1 ≤ n ≤ 10^9) - the number of rails. The subsequent lines contain queries of three types:
I a b D - configuration change. Rails from the a-th to the b-th inclusive will have an incline of D after executing this query.
Q h - cart launch. Determine the number of rails the cart, capable of reaching a height of h, will pass.
E - end of input data. This query will appear exactly once at the end of the file.
At any time, the height of any point on the track is within the range from 0 to 10^9. There are no more than 100000 lines in the input.
Output
For each Q query, output a single integer - the number of rails the cart will pass.