题目描述

日本列岛是一条东西向狭长的群岛。日本列岛被南北方向的边界线划分为 $N$ 个区域，这些区域从西向东依次编号为 $1$ 至 $N$。当前，区域 $i$（$1 \le i \le N$）的海拔为 $A_i\ \text{m}$。

日本列岛上时常刮起强风。强风会引起海浪，导致各区域的海拔按以下方式下降：

• 当刮起强度为 $x$ 的西风时，在从西数起的 $x$ 个区域中，所有满足“其西侧不存在比自身海拔更高的区域”的区域，其海拔将减少 $1\ \text{m}$。换言之，若风暴前区域 $i$ 的海拔为 $a_i$，且满足 $i \le x$，并对所有满足 $1 \le k < i$ 的 $k$ 均有 $a_k \le a_i$，则区域 $i$ 的海拔减少 $1\ \text{m}$；其他情况下海拔不变。
• 当刮起强度为 $x$ 的东风时，在从东数起的 $x$ 个区域中，所有满足“其东侧不存在比自身海拔更高的区域”的区域，其海拔将减少 $1\ \text{m}$。换言之，若风暴前区域 $i$ 的海拔为 $a_i$，且满足 $i \ge N - x + 1$，并对所有满足 $i < k \le N$ 的 $k$ 均有 $a_k \le a_i$，则区域 $i$ 的海拔减少 $1\ \text{m}$；其他情况下海拔不变。

你必须模拟未来 $Q$ 天内发生的事件。第 $j$ 天（$1 \le j \le 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\ \cdots\ A_N$

$T_1\ X_1$

$T_2\ X_2$

$\vdots$

$T_Q\ X_Q$

输出格式

对于每一个满足 $T_j = 3$ 的 $j$（$1 \le j \le Q$），请在一行中输出第 $j$ 天时区域 $X_j$ 的海拔（单位：米），以整数形式表示。

5 7
7 7 7 7 7
1 3
1 1
3 1
2 1
2 5
3 2
3 4

5
6
6

5 7
10 13 14 7 12
1 5
2 5
3 3
3 4
2 5
3 1
3 2

12
7
9
11

5 6
8 6 7 8 9
1 1
3 1
3 5
1 3
3 2
3 3

7
9
6
6

5 6
6 8 6 9 7
2 1
2 4
3 5
1 5
3 4
3 3

5
7
6

提示

数据范围

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

子任务

1. （5 分）$N \le 2\,000$，$Q \le 2\,000$。
2. （27 分）若 $T_j \ne 3$，则 $X_j = N$（$1 \le j \le Q$）。
3. （28 分）$A_1 = A_2 = \cdots = A_N = Q$。
4. （20 分）$T_j \ne 2$（$1 \le j \le Q$）。
5. （20 分）无额外约束。

翻译由 Qwen3-235B 完成。