题目描述

给定一个长度为 $n$ 的序列 $a$，要求支持如下三个操作：

1. 给定区间 $[l, r]$，将区间内每个数都修改为 $x$。
2. 给定区间 $[l, r]$，将区间内每个数都加上 $x$。
3. 给定区间 $[l, r]$，求区间内的最大值。

输入格式

第一行是两个整数，依次表示序列的长度 $n$ 和操作的个数 $q$。
第二行有 $n$ 个整数，第 $i$ 个整数表示序列中的第 $i$ 个数 $a_i$。
接下来 $q$ 行，每行表示一个操作。每行首先有一个整数 $op$，表示操作的类型。

• 若 $op = 1$，则接下来有三个整数 $l, r, x$，表示将区间 $[l, r]$ 内的每个数都修改为 $x$。
• 若 $op = 2$，则接下来有三个整数 $l, r, x$，表示将区间 $[l, r]$ 内的每个数都加上 $x$。
• 若 $op = 3$，则接下来有两个整数 $l, r$，表示查询区间 $[l, r]$ 内的最大值。

输出格式

对于每个 $op = 3$ 的操作，输出一行一个整数表示答案。

6 6
1 1 4 5 1 4
1 1 2 6
2 3 4 2
3 1 4
3 2 3
1 1 6 -1
3 1 6

7
6
-1

4 4
10 4 -3 -7
1 1 3 0
2 3 4 -4
1 2 4 -9
3 1 4

0

提示

数据规模与约定

• 对于 $10\%$ 的数据，$n = q = 1$。
• 对于 $40\%$ 的数据，$n, q \leq 10^3$。
• 对于 $50\%$ 的数据，$0 \leq a_i, x \leq 10^4$。
• 对于 $60\%$ 的数据，$op \neq 1$。
• 对于 $90\%$ 的数据，$n, q \leq 10^5$。
• 对于 $100\%$ 的数据，$1 \leq n, q \leq 10^6$，$1 \leq l, r \leq n$，$op \in \{1, 2, 3\}$，$|a_i|, |x| \leq 10^9$。

提示

请注意大量数据读入对程序效率造成的影响。