Array Operations and Auxiliary Array Maintenance

Given a sequence (A = [A_1, A_2, \dots, A_n]) and an auxiliary sequence (B) initially identical to (A), perform (m) operations. There are five types of operations provided in the following formats:

1. (1\ l\ r\ k): For all (i \in [l, r]), update (A_i \gets A_i + k) ((k) can be negative).
2. (2\ l\ r\ v): For all (i \in [l, r]), update (A_i \gets \min(A_i, v)).
3. (3\ l\ r): Output (\sum_{i=l}^{r} A_i).
4. (4\ l\ r): Output (\max{A_i \mid i \in [l, r]}).
5. (5\ l\ r): Output (\max{B_i \mid i \in [l, r]}).

After each operation, for all (i \in [l, r]) the auxiliary array is updated as follows: [ B_i \gets \max(B_i, A_i). ]

Process all operations in order and output the results for each operation of type (3), (4), and (5).

inputFormat

The first line contains two integers (n) and (m), representing the number of elements and the number of operations, respectively.\nThe second line contains (n) integers, which are the elements of the initial sequence (A).\nThe following (m) lines each describe an operation in one of the following formats:

• (1\ l\ r\ k)
• (2\ l\ r\ v)
• (3\ l\ r)
• (4\ l\ r)
• (5\ l\ r)

outputFormat

For every operation of type (3), (4), or (5), output the corresponding result on a single line.

sample

5 5
1 2 3 4 5
1 1 3 10
3 1 5
2 2 4 5
4 1 3
5 3 5

45
11
13