collectmushrooms

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 D_i. 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, |D_i, Y| ≤ 10⁹, 0 ≤ T ≤ 1

Subtask 1 (18%): 1 ≤ N, M ≤ 500000, T = 0. There will be no updates. D_i = 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.