给定一个长度为 $n$ 的序列 $A_1, A_2, \cdots, A_n$，你需要进行 $m$ 次以下操作：

• 1 l r x： 对每个 $l \leq i \leq r$，令 $A_i \leftarrow A_i + x$。
• 2 l r x：对每个 $1 \leq i \leq r$，令 $A_i \leftarrow x$。
• 3 l r：询问满足 $l \leq i \leq r$ 的 $A_i$ 的最大值。
• 4 l r：询问满足 $l \leq i \leq r$ 的 $A_i$ 的历史最大值。

输入格式

输入的第一行包含两个整数 $n, m$，表示序列的长度与操作次数。

接下来一行，包含 $n$ 个整数 $A_1, A_2, \cdots, A_n$，表示初始时序列 $A$ 的值。

接下来 $m$ 行，每行包含若干个整数，描述一个操作。

输出格式

对于所有询问操作，输出一行一个整数，表示答案。

样例数据

样例 1 输入

5 10
-5 6 -10 3 8 
4 3 5
4 2 4
1 4 4 -7
1 3 3 1
4 1 1
1 2 4 7
1 1 4 9
2 1 3 9
3 1 1
4 4 5

样例 1 输出

8
6
-5
9
12

样例 2 输入

6 12
-5 4 -3 0 9 6
3 1 5
2 2 4 2
1 1 3 5
1 3 5 -4
2 4 5 1
4 1 6
1 3 6 2
4 1 2
3 5 6
1 1 6 -1000000000
3 2 4
4 2 4

样例 2 输出

9
9
7
8
-999999993
7

样例 3 输入

20 30
-300641398 643562768 -973662722 -828209263 -309447205 -598693447 -101747247 -218359912 223156787 144550482 -764855619 527931534 652711445 -378234863 -861768168 -746317163 954632121 -742544956 -683774548 206177971 
1 10 17 -978752351
3 6 20
2 12 19 -52976069
2 14 18 -820873406
2 5 13 -809636884
2 1 15 -92483004
1 3 5 697386996
1 9 14 -199066725
2 1 6 -420516547
4 1 14
1 17 19 754289671
4 8 12
1 9 12 771518399
2 7 13 -343914441
3 3 19
2 9 13 360029137
3 1 12
2 2 8 616334876
2 15 15 -469894325
1 6 9 -721353073
1 3 5 335823776
1 4 6 -811222500
4 7 11
1 2 5 -621714033
2 5 16 165108179
2 16 19 -650336428
4 9 11
1 11 14 644010439
4 6 13
4 4 12

样例 3 输出

223156787
652711445
527931534
701313602
360029137
616334876
479968670
809118618
952158652

子任务

对于所有数据，$1 \leq n,m \leq 5 \times 10^5, -10^9 \leq A_i \leq 10^9, 1 \leq l \leq r \leq n, -10^9 \leq x \leq 10^9$。

• Subtask 1(10 points): $1 \leq n,m \leq 5000$
• Subtask 2(20 points): 不存在操作 $1$。
• Subtask 3(20 points): 不存在操作 $2$。
• Subtask 4(50 ponits): 没有额外的限制。