Given a sequence $A_1, A_2, \cdots, A_n$ with the length $n$. You need to process the following $m$ queries:

• 1 l r x: For each $l \leq i \leq r$, let $A_i \leftarrow A_i + x$.
• 2 l r x: For each $l \leq i \leq r$, let $A_i \leftarrow x$.
• 3 l r: Print the maximum value of $A_i$ when $l \leq i \leq r$.
• 4 l r: Print the historical maximum value of $A_i$ when $l \leq i \leq r$.

Input

The first line of the input contains two integers $n$ and $m$ - the length of the sequence and the number of the operations.

The next line of the input contains $n$ integers $A_1, A_2, \cdots, A_n$, describes the sequence $A$ at the initial time.

The next $m$ lines of the input describe one query per line.

Output

For each query of type 3 or 4, you need to output a line with a single integer indicating the answer.

Samples

Input 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

Output 1

8
6
-5
9
12

Input 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

Output 2

9
9
7
8
-999999993
7

Input 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

Output 3

223156787
652711445
527931534
701313602
360029137
616334876
479968670
809118618
952158652

Scoring

It is guaranteed that $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): there's no query of type 1.
• Subtask 3(20 points): there's no query of type 2.
• Subtask 4(50 ponits): no additional constraints.