序列

题目描述

给定一个长度为 $n$ 的序列,给出 $q$ 个操作,形如: $1~l~r~x$ 表示将序列下标介于 $[l,r]$ 的元素加上 $x$ (请注意,$x$ 可能为负) $2~p~y$ 表示查询 $a_p$ 在过去的多少秒时间内不小于 $y$ (不包括这一秒,细节请参照样例) 开始时为第 $0$ 秒,第 $i$ 个操作发生在第 $i$ 秒。

输入输出格式

输入格式


第一行两个整数 $n,q$,意义如描述所述。 接下来一行 $n$ 个整数 $a_i$,表示序列的每个元素的初始值。 接下来 $q$ 行,每行第一个数为 $\text{opt}$,表示这次操作的类型。如果 $\text{opt} = 1$,后面紧跟三个整数 $l, r, x$,意义如描述所述;如果 $\text{opt} = 2$,后面紧跟两个整数 $p, y$,意义如描述所述。

输出格式


对于每个操作 $2$,在一行内输出一个数表示答案。

输入输出样例

输入样例 #1

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

输出样例 #1

0
2

说明

样例一说明:位置 $1$ 在第 $0$ 秒到第 $3$ 秒的值为 $1,1,-2,-2$。对于第一个查询,前 $1-1=0$ 秒中有 $0$ 秒时间不小于 $2$;对于第二个查询,前 $3-1=2$ 秒中有 $2$ 秒时间不小于 $1$,分别为第 $0$ 秒,第 $1$ 秒。 对于 $30\%$ 的数据,保证 $n,q \leq 1000$ 对于 $70\%$ 的数据,保证 $n,q \leq 50000$ 对于 $100\%$ 的数据,保证 $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$