题目描述

区间赋值 + 区间加 + 区间最大值 给定一个长度为 n 的序列 a，要求支持如下三个操作： 1、给定区间 [l,r]，将区间内每个数都修改为 x。 2、给定区间 [l,r]，将区间内每个数都加上 x。 3、给定区间 [l,r]，求区间内的最大值。

输入格式

第一行是两个整数，依次表示序列的长度 n 和操作的个数 q。 第二行有 n 个整数，第 i 个整数表示序列中的第 i 个数 ai 。 接下来 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 的操作，输出一行一个整数表示答案。

样例

输入样例 1

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

输出样例 1

7
6
-1

输入样例 2

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

输出样例 2

0

输入样例 3

24 13
6506 4278 938 1847 4933 162 9565 7052 963 7419 320 434 823 4160 8160 9844 9825 1131 5447 2113 9953 8685 8585 3850
1 20 24 -2
2 4 19 200
3 1 18
3 7 24
2 18 20 -20
2 13 24  10
3 4 15
1 19 24 18
3 8 24
1 5 20 6918
2 1 21 918
3 13 19
3 1 24

输出样例 3

10044
10044
9765
10054
7836
7836

提示

数据规模与约定：1≤n,q≤10^6，1≤l,r≤n，op∈{1,2,3}，|a|,|x|≤10^9