Simulated Roller Coaster Ride

A new simulation roller coaster ride has been launched. The track consists of n rail segments arranged in a loop. The ride starts at height 0, and each segment i has a height difference d_i. Thus, when arriving at segment i with current height h, after passing segment i the height becomes h + d_i.

Initially, the track is a horizontal line, i.e. for all i we have d_i=0. During the day, two types of operations occur in an arbitrary order:

• Run operation: A number h is given, representing the maximum height the car can reach. Starting at height 0, the car traverses the segments in order. It proceeds segment by segment and stops as soon as the cumulative height would exceed h. The answer for a run operation is the number of segments the car completes before stopping. (If the car manages to complete all segments while its height never exceeds h, output n.)
• Modification operation: Three integers a, b and D are given (with 1 ≤ a ≤ b < n). The operator adjusts the track as follows: the segments from a to b (inclusive) are set to have height difference D. In order to keep the track connected and ensure that the starting height remains 0, all segments after segment b (in the order of travel) are adjusted by adding a constant offset. Specifically, let
  \( \delta = (b - a + 1) \times D - \sum_{i=a}^{b} d_i \),

  then for every segment i with i > b, update:

  \( d_i \leftarrow d_i - \frac{\delta}{n-b} \).

  Segments before a remain unchanged. It is guaranteed that after every modification the total change over one cycle remains 0, that is, (\sum_{i=1}^{n} d_i = 0).

Your task is to process a sequence of operations and for each run operation output the number of rails the car passes before stopping.

inputFormat

The first line contains two integers n and q, the number of segments and the number of operations.

Each of the next q lines represents an operation. An operation is either:

• A single integer h representing a run operation;
• Or three integers a b D representing a modification operation which sets segments a to b to have height difference D and adjusts the following segments as described.

It is guaranteed that for every modification operation, 1 ≤ a ≤ b < n and initially all di are 0 and \(\sum_{i=1}^{n} d_i = 0\).

outputFormat

For each run operation, output a single integer, the number of rail segments the car completes before stopping, each on its own line.

sample

5 5
10
2 4 3
5
1 2 -1
3

5
2
3