Time-Traveling Array Queries

You are given a sequence of n integers and q operations. The operations occur in chronological order with the initial state at second 0 and each subsequent operation at seconds 1 through q.

There are two types of operations:

• Update: 1 l r x — For every index i in the interval [l, r], add x to a_i. Note that x may be negative.
• Query: 2 p y — At the current time t, determine for how many consecutive past seconds s (starting from t-1 and moving backwards) the value a_p was at least y. The current second is not included in the count.

The value of a_p at any second t is defined as:

where \(\Delta_i(p)\) is the change applied at second \(i\) (if any) to index p.

inputFormat

The first line contains two integers n and q.

The second line contains n integers representing the initial sequence, a₁, a₂, \ldots, a_n.

The following q lines each represent an operation, either in the form:

• 1 l r x (update operation), or
• 2 p y (query operation).

All indices are 1-indexed.

outputFormat

For each query (operation of type 2), output one line with a single integer representing the number of consecutive seconds (immediately preceding the current second) during which a_p was at least y.

sample

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

1
3
0