题目描述

33DAI 有一个长度为 $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：在第一个元素后面插入 $7$，序列变为 1 7 2 3 4 5。
• 1 2 4：查询第 $2$ 到第 $4$ 个元素 (7 2 3) 的最大值，输出 $7$。
• 4 2 5：删除第 $2$ 到第 $5$ 个元素，序列变为 1 5。
• 3 1 10：把第 $1$ 个元素改为 $10$，序列变为 10 5。
• 1 1 2：查询第 $1$ 到第 $2$ 个元素 (10 5) 的最大值，输出 $10$。

数据范围与提示

• 子任务 1（30 分）：只有操作 1 和操作 2，且保证每次操作 1 对应的 $x, y$ 都是从 $1$ 到当前数组长度。
• 子任务 2（30 分）：只有操作 1 和操作 3。
• 子任务 3（40 分）：无特殊限制。
• 对于 $100\%$ 的数据，$1 \le n, m \le 100$，$1 \le a_i \le 10^9$，保证所有操作合法，且插入或修改的数在 $1 \sim 10^9$ 范围内。