题目背景

Subtask 0 为原数据，Subtask 1 为 hack 数据。

题目描述

在一条笔直的道路上从左到右一共有 $n$ 片区域，每一片区域一开始都种着一棵树，其中第 $i$ 片区域种着高度为 $h_i$ 的树。接下来你需要处理 $q$ 个操作：

• 1 l r c：将第 $l$ 片区域到第 $r$ 片区域内的所有树的高度拔高 $c$ 个单位。
• 2 l r h：将一把刀固定在高度为 $h$ 的空中，对第 $l$ 片区域到第 $r$ 片区域内的所有树进行砍伐。
• 3 l r h：往第 $l$ 片区域到第 $r$ 片区域内的每个区域种上一棵高度为 $h$ 的树。
• 4 l r：查询第 $l$ 片区域到第 $r$ 片区域内最高的树的高度。

注：本题中的高度为相对于某个水平面的高度，也就是说可能会有负数的出现。

输入格式

第一行，两个整数 $n, q$；

第二行，$n$ 个整数 $h_1, h_2, \cdots, h_n$；

接下来 $q$ 行，每行三或四个整数 $op, l, r, c$、$op, l, r, h$ 或 $op, l, r$。

输出格式

若干行，每行一个整数，表示对应查询的结果。

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

7
8
8

提示

对于 $100\%$ 的数据，$1 \leq n, q \leq 5 \times 10^5$，$1 \leq h_i \leq 10^9$，$1 \leq l \leq r \leq n$，$0 \leq |c| \leq 500$，$1 \leq h \leq 10^9$。