Problem Description
Peanut owns a mushroom farm and wants to collect some mushrooms. His mushroom farm has N mushrooms in a row, numbered 0 to N-1 from left to right. Each mushroom i has deliciousness Di. Some mushrooms can be rotten, and so can have negative deliciousness. He assigns M minions to help him collect some mushrooms. Each minion i will be assigned a range A to B. Minions tend to fight each other, so Peanut will assign them ranges which do not intersect. However, each minion can only carry at most 1 mushroom, since they have small hands.
Also, minions sometimes rebel and decide to enhance or damage a mushroom. When this happens, the quality of mushroom at X will change to Y.
Help Peanut find the maximum deliciousness each minion can collect. Minions that are collecting mushrooms have to collect 1 mushroom.
Input
The first line contains the number N and M.
The second line contains N numbers, representing the array D.
M lines will follow. The first character of each line will be T.
If T is 0, then it represents a query. 2 integers will then follow, A and B.
If T is 1, then it represents a update. 2 integers will then follow, X, Y.
Output
For each line of query, you are to output the maximum deliciousness of mushrooms collected on a single line.
Limits
For all subtasks: 0 ≤ A≤ B< N, 0 ≤ X < N, |Di, Y| ≤ 109, 0 ≤ T ≤ 1
Subtask 1 (18%): 1 ≤ N, M ≤ 500000, T = 0. There will be no updates. Di = i for all i.
Subtask 2 (29%): 1 ≤ N, M ≤ 500000, T = 0. There will be no updates.
Subtask 3 (53%): 1 ≤ N, M ≤ 500000.
Subtask 4 (0%): Sample Testcases.
Sample Input 1
5 4
3 1 4 2 5
0 0 1
1 1 -3
1 3 6
0 2 4
Sample Output 1
3
6
Explanation
Farm has initial mushroom values: 3 1 4 2 5
Minion picks mushroom at position 0.
Minion damages mushroom 1. Farm has mushrooms values: 3 -3 4 2 5
Minion enhances mushroom 3. Farm has mushroom values: 3 -3 4 6 5
Minion picks mushroom at position 3.