日本列岛是一个东西向狭长的群岛。日本列岛被南北方向的分界线分成 $N$ 个区块。区块从西到东依次编号为 $1$ 到 $N$。现在，第 $i$ 个区块（$1 \leq i \leq N$）的海拔为 $A_i\:\mathrm{m}$。

在日本列岛上经常会发生暴风雨。每当暴风雨来临时，海浪会导致各区块的海拔按如下方式降低：

• 对于强度为 $x$ 的西风暴风雨，在从西数不超过 $x$ 个的区块中，所有“在其西侧不存在比自身海拔更高的区块”的区块，其海拔都会减少 $1\:\mathrm{m}$。即，若暴风雨发生前第 $i$ 个区块的海拔为 $a_i$，只有当 $i \leq x$，并且对所有满足 $1 \leq k < i$ 的 $k$ ，$a_k \leq a_i$，此时第 $i$ 个区块海拔减少 $1\:\mathrm{m}$，否则保持不变。
• 对于强度为 $x$ 的东风暴风雨，在从东数不超过 $x$ 个的区块中，所有“在其东侧不存在比自身海拔更高的区块”的区块，其海拔都会减少 $1\:\mathrm{m}$。即，若暴风雨发生前第 $i$ 个区块的海拔为 $a_i$，只有当 $i \geq N - x + 1$，并且对所有满足 $i < k \leq N$ 的 $k$，$a_k \leq a_i$，此时第 $i$ 个区块海拔减少 $1\:\mathrm{m}$，否则保持不变。

你需要模拟接下来 $Q$ 天内发生的事件。第 $j$ 天（$1 \leq j \leq Q$）发生如下事件之一：

• 若 $T_j = 1$，则发生一次强度为 $X_j$ 的西风暴风雨。
• 若 $T_j = 2$，则发生一次强度为 $X_j$ 的东风暴风雨。
• 若 $T_j = 3$，则需要报告此时第 $X_j$ 个区块的海拔。

保证任何区块的海拔都不会变成负数。

给定每个区块当前的海拔和接下来 $Q$ 天的事件，请写程序，对于每一个 $T_j = 3$ 的那一天，输出指定区块的当前海拔。

输入格式如下：

$N$ $Q$ $A_1$ $A_2$ $\dots$ $A_N$ $T_1$ $X_1$ $T_2$ $X_2$ $\vdots$ $T_Q$ $X_Q$

对于每一个 $T_j = 3$ 的 $j$（$1 \leq j \leq Q$），按顺序每行输出第 $j$ 天时指定区块的海拔（单位：$\mathrm{m}$）。

子任务

1.（$5$ 分）$N \leq 2\,000$，$Q \leq 2\,000$。
2.（$27$ 分）若 $T_j \neq 3$，则 $X_j = N$（$1 \leq j \leq Q$）。
3.（$28$ 分）$A_1 = A_2 = \cdots = A_N = Q$。
4.（$20$ 分）不存在 $T_j = 2$（$1 \leq j \leq Q$）。
5.（$20$ 分）无其他额外限制。

样例解释 1

区块 $1,2,3,4,5$ 的海拔 $[m]$

事件	处理后各区块海拔
初始	$7, 7, 7, 7, 7$
第1天 持续强度为3的西风暴风雨	西面前3个区块中，没有更西侧比本身更高的区块的是 1,2,3 区块 → $6, 6, 6, 7, 7$
第2天 持续强度为1的西风暴风雨	西面第1个区块中，没有更西侧比本身更高的区块是 1 区块 → $5, 6, 6, 7, 7$
第3天 查询1号区块的海拔	$5$
第4天 持续强度为1的东风暴风雨	东面第1个区块中，没有更东侧比本身更高的区块是 5 区块 → $5, 6, 6, 7, 6$
第5天 持续强度为5的东风暴风雨	东面前5个区块中，没有更东侧比本身更高的区块是 4,5 区块 → $5, 6, 6, 6, 5$
第6天 查询2号区块的海拔	$6$
第7天 查询4号区块的海拔	$6$

本样例满足子任务 $1, 3, 5$ 的限制条件。

样例解释 2

本样例满足子任务 $1, 2, 5$ 的限制条件。

样例解释 3

本样例满足子任务 $1, 4, 5$ 的限制条件。

样例解释 4

本样例满足子任务 $1, 5$ 的限制条件。

数据范围与限制

• $1 \leq N \leq 300\,000$。
• $1 \leq Q \leq 300\,000$。
• $Q \leq A_i \leq 10^9$（$1 \leq i \leq N$）。
• $1 \leq T_j \leq 3$（$1 \leq j \leq Q$）。
• $1 \leq X_j \leq N$（$1 \leq j \leq Q$）。
• 输入数据均为整数。

由 ChatGPT 5 翻译