有一个长条形的水池,可以划分成 n 格。其中第 i 格和 i+1 格之间相邻,由一块高度为 hi 的可调节挡板隔开。第 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 个正整数 h1,h2,…,hn−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≤n,q≤2×105,0≤hi≤109。
- 对于 10% 的数据,n≤500;
- 对于另外 20%,没有操作 1,且 i 从 0 开始连续增长(不需要可持久化);
- 对于另外 20%,没有操作 1;
- 对于另外 20%,且 i 从 0 开始连续增长(不需要可持久化);
- 对于余下 30% 的数据,无特殊限制。