有一个长条形的水池，可以划分成 $n$ 格。其中第 $i$ 格和 $i+1$ 格之间相邻，由一块高度为 $h_i$ 的可调节挡板隔开。第 $1$ 格左侧和第 $n$ 格右侧是无限高的池壁。初始时水池中没有水。现在进行 $q$ 次操作，操作有以下四种：

• 0 i x h 在第 $x$ 格灌水直到该格的水面高度不低于 $h$（若当前水面高度已经达到 $h$ 则无事发生）；
• 1 i x 打开第 $x$ 格底部的排水口直到该格的水流干，再关闭排水口；
• 2 i x h 将第 $x$ 格右侧的挡板高度增加到 $h$（不改变现有水面，保证挡板高度不会下降）；
• 3 i x 查询第 $x$ 格的水面高度。

其中，$i$ 表示这次操作是基于第 $i$ 次操作之后的情况，$i=0$ 表示基于初始状态。也就是说，这个问题要求对操作可持久化。

输入格式

第一行两个自然数 $n,q$，表示水池格数和操作次数。

接下来一行 $n-1$ 个正整数 $h_1, h_2, \dots, h_{n-1}$ 表示挡板的初始高度。

接下来 $q$ 行每行一个正整数表示一次操作。

输出格式

对每个操作 $3$ 输出一行一个整数表示答案。

样例数据

样例输入

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

样例输出

0
0
4
4

样例解释

子任务

对于所有数据，$1\le n,q\le 2\times 10^5, 0\le h_i\le 10^9$。

• 对于 $10\%$ 的数据，$n\le 500$；
• 对于另外 $20\%$，没有操作 $1$，且 $i$ 从 $0$ 开始连续增长（不需要可持久化）；
• 对于另外 $20\%$，没有操作 $1$；
• 对于另外 $20\%$，且 $i$ 从 $0$ 开始连续增长（不需要可持久化）；
• 对于余下 $30\%$ 的数据，无特殊限制。