时空限制

1S/512M

题目描述

apiadu 养了 $n$ 盆盆栽，编号为 $1$ 到 $n$。最开始（时刻 $0$），第 $i$ 盆盆栽的土壤水分含量为 $a_i$。

由于水分会自然蒸发，盆栽的水分含量会随着时间自动下降：如果一盆盆栽在某段时间内没有被浇水，那么每经过 $1$ 单位时间，它的水分含量就会减少 $1$。但水分含量最低不会降到 $0$ 以下。

接下来有 $q$ 个事件按时间顺序发生。第 $j$ 个事件发生在时刻 $t_j$，保证时间递增，即 $0 < t_1 < t_2 < \dots < t_q$。

事件共有以下两种类型：

• 1 t x v：在时刻 $t$，往第 $x$ 盆盆栽中浇水，使其水分增加 $v$。
• 2 t x：在时刻 $t$，询问第 $x$ 盆盆栽当前的水分含量。

请按顺序处理所有的事件，并输出所有类型为 2 的事件的答案。

格式

输入格式

第一行包含两个正整数 $n$ 和 $q$，分别表示盆栽的数量和事件的数量。

第二行包含 $n$ 个非负整数 $a_1, a_2, \dots, a_n$，表示每盆盆栽在时刻 $0$ 的初始水分含量。

接下来 $q$ 行，每行描述一个事件：

• 若格式为 1 t x v，表示往第 $x$ 盆盆栽浇水 $v$；

• 若格式为 2 t x，表示询问第 $x$ 盆盆栽的水分。

输出格式

对于每个类型为 2 的询问事件，输出一行一个整数，表示对应盆栽在当前时刻的水分含量。

样例

样例输入 #1

3 8
5 0 4
2 1 1
1 2 2 6
2 4 2
1 6 1 3
2 7 1
2 9 3
1 10 3 5
2 12 3

样例输出 #1

4
4
2
0
3

样例解释 #1

各盆栽的初始水分含量为 $[5, 0, 4]$。

1. 2 1 1：第 $1$ 盆在时刻 $1$ 的水分为 $5-1=4$，输出 $4$。
2. 1 2 2 6：第 $2$ 盆在时刻 $2$ 的水分仍为 $0$，浇水后变为 $6$。
3. 2 4 2：第 $2$ 盆距离上次浇水经过 $2$ 单位时间，水分变为 $4$，输出 $4$。
4. 1 6 1 3：第 $1$ 盆到时刻 $6$ 已蒸发到 $0$，浇水后变为 $3$。
5. 2 7 1：第 $1$ 盆距离上次浇水经过 $1$ 单位时间，水分变为 $2$，输出 $2$。
6. 2 9 3：第 $3$ 盆从时刻 $0$ 到时刻 $9$ 未被浇水，水分降至 $0$，输出 $0$。
7. 1 10 3 5：第 $3$ 盆在时刻 $10$ 的水分为 $0$，浇水后变为 $5$。
8. 2 12 3：第 $3$ 盆距离上次浇水经过 $2$ 单位时间，水分变为 $3$，输出 $3$。

样例输入 #2

1 5
100
1 1 1 5
2 3 1
1 10 1 4
2 11 1
2 20 1

样例输出 #2

102
98
89

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

子任务编号	分数	$n, q\le$
$1$	$40$	$2000$
$2$	$60$	$2\times 10^5$

对于 $100\%$ 的数据，$1 \le n, q \le 2 \times 10^5$，$0 \le a_i \le 10^9$，事件中的 $t$ 按升序给出，且 $1 \leq t_i \le 10^9$，$1 \le x \le n$，$1 \le v \le 10^9$。