#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

## 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.

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 18 | 20 | 0.5s | 256MB | Minimum |

2 | 29 | 40 | 0.5s | 256MB | Minimum |

3 | 53 | 61 | 0.5s | 256MB | Minimum |

4 | 0 | 1 | 0.5s | 256MB | Minimum |

### Judge Compile Command

g++-7 ans.cpp -o collectmushrooms -Wall -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512