You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

Csvoner 有一个长度为 $n$ 的序列：$a_1\sim a_n$。他想对这个序列进行 $m$ 次操作，每次操作用如下形式之一描述：

• 1 x y：查询 $a_x\sim a_y$ 的最大值
• 2 x y：在 $a_x$ 的后面插入一个新的数 $y$
• 3 x y：把 $a_x$ 修改为 $y$
• 4 x y：把 $a_x\sim a_y$ 这些数都删除。

输入格式

第一行两个整数：$n,m$。

第二行为空格隔开的 $n$ 个正整数：$a_1\sim a_n$。

接下来 $m$ 行，每行都是空格隔开的三个整数，操作如上所述。

输出格式

对于每个 1 操作，输出一行，为对应的最大值。

5 6
1 2 3 4 5 
1 1 5
2 1 7
1 2 4
4 2 5
3 1 10
1 1 2

5
7
10

样例解释

• 初始：1 2 3 4 5。
• 1 1 5：(1 2 3 4 5) 最大值为 $5$。
• 2 1 7：1 7 2 3 4 5 插入了一个 $7$ 在第一个元素后面。
• 1 2 4：1 (7 2 3) 4 5 最大值为 $7$。
• 4 2 5：1 5 删除了中间的 7 2 3 4
• 3 1 10：10 5 把第一个 $1$ 改成了 $10$
• 1 1 2：(10 5) 最大值为 $10$

数据规模与约定

对于 $100\%$ 的数据，$1 \le n,m\le 100$，$1\le a_i\le 10^9$，保证所有操作合法，且如果是插入或修改，那么插入或修改的数也在 $1\sim 10^9$ 范围内。

• 子任务 1（30 分）：只有操作 1 （查询）和操作 2（插入），且保证每次操作 1 对应的 x y 都是从 1 到当时的数组长度（查整个序列的最大值）。
• 子任务 2（30 分）：保证只有操作 1（查询）和操作 3（修改）。
• 子任务 3（40 分）：没有特殊限制。