Description

Given a sequence of length $n$, there are $q$ operations of the following forms.

$1~l~r~x$ means adding $x$ to each element with index in $[l,r]$ (note that $x$ may be negative).

$2~p~y$ means querying for how many seconds in the past $a_p$ has been at least $y$ (excluding the current second; see the sample for details).

Time starts at second $0$, and the $i$-th operation occurs at second $i$.

Input Format

The first line contains two integers $n,q$, as described.

The second line contains $n$ integers $a_i$, the initial values of the sequence.

Each of the next $q$ lines starts with $\text{opt}$, indicating the type of this operation. If $\text{opt} = 1$, it is followed by three integers $l, r, x$, as described. If $\text{opt} = 2$, it is followed by two integers $p, y$, as described.

Output Format

For each operation of type $2$, output one integer on a single line indicating the answer.

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

0
2

Hint

Explanation for Sample 1: at position $1$, the values from second $0$ to second $3$ are $1,1,-2,-2$. For the first query, during seconds $0$ to $1-1=0$, the value is not less than $2$. For the second query, during seconds $0$ to $3-1=2$, the value is not less than $1$, namely at second $0$ and second $1$.

For $30\%$ of the testdata, $n,q \leq 1000$.

For $70\%$ of the testdata, $n,q \leq 50000$.

For $100\%$ of the testdata, $2 \leq n,q \leq 100000$, $1 \leq l \leq r \leq n$, $1 \leq p \leq n$, $-10^9 \leq x,y,a_i \leq 10^9$.

Translated by ChatGPT 5