### ** 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^{9}, 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.