PROGRAMMING:Summation of maximal continuous subsets in a Treap interval
Because dhxh's language is so poor that he can't even make up the question. So he decided to go straight to the point. Now dhxh has a sequence a with n terms. There are two operations. Operation 1: insert a number x after the k-th number; Operation 2: ask the sum of the largest continuous sub segments of the interval [l, R]. M operations in total.
###Input format:
In the first line, there are two integers n and m, meaning as described in the title. In the second line, there are n integers representing the sequence a
The next M lines are three integers per line. The first integer in each row is p. If P = 1, then the next two numbers are k, X and perform operation one; If P = 2, then the next two numbers are l, R and perform operation two.
###Output format:
For each operation two, output a line of query results
###Input sample 1:
Here is a set of inputs. For example:
```in
5 1
1 5 -7 9 4
2 1 5
```
###Output sample 1:
The corresponding output is given here. For example:
```out
thirteen
```
###Input sample 2:
Here is a set of inputs. For example:
```in
5 5
63 100 -58 88 45
1 4 -17
1 6 -91
1 7 -25
2 1 7
2 5 8
```
###Output sample 2:
The corresponding output is given here. For example:
```out
two hundred and twenty-one
forty-five
```
###Exemplar explanation
In example 1, the maximum sum of consecutive fields in [1,5] is 9 + 4 = 13
In example 2, the sequence after insertion is 63, 100, − 58, 88, − 17, 45, − 91, − 25, so the maximum continuous field sum in [1, 7] is 63 + 100 − 58 + 88 −
17 + 45 = 221, and the maximum sum of consecutive fields in [5, 8] is 45
###Data range
For 30% data, 1 ≤ n ≤ 500, 1 ≤ m ≤ 500 are guaranteed
Another 20% of the data guarantees only query operation
For 70% data, 1 ≤ n ≤ 3 × 104, 1 ≤ M ≤ 3 × one hundred and four
For 100% data, ensure 1 ≤ n ≤ 105, 1 ≤ m ≤ 105, − 106 ≤ x ≤ 106
answer：If there is no answer, please comment
###Input format:
In the first line, there are two integers n and m, meaning as described in the title. In the second line, there are n integers representing the sequence a
The next M lines are three integers per line. The first integer in each row is p. If P = 1, then the next two numbers are k, X and perform operation one; If P = 2, then the next two numbers are l, R and perform operation two.
###Output format:
For each operation two, output a line of query results
###Input sample 1:
Here is a set of inputs. For example:
```in
5 1
1 5 -7 9 4
2 1 5
```
###Output sample 1:
The corresponding output is given here. For example:
```out
thirteen
```
###Input sample 2:
Here is a set of inputs. For example:
```in
5 5
63 100 -58 88 45
1 4 -17
1 6 -91
1 7 -25
2 1 7
2 5 8
```
###Output sample 2:
The corresponding output is given here. For example:
```out
two hundred and twenty-one
forty-five
```
###Exemplar explanation
In example 1, the maximum sum of consecutive fields in [1,5] is 9 + 4 = 13
In example 2, the sequence after insertion is 63, 100, − 58, 88, − 17, 45, − 91, − 25, so the maximum continuous field sum in [1, 7] is 63 + 100 − 58 + 88 −
17 + 45 = 221, and the maximum sum of consecutive fields in [5, 8] is 45
###Data range
For 30% data, 1 ≤ n ≤ 500, 1 ≤ m ≤ 500 are guaranteed
Another 20% of the data guarantees only query operation
For 70% data, 1 ≤ n ≤ 3 × 104, 1 ≤ M ≤ 3 × one hundred and four
For 100% data, ensure 1 ≤ n ≤ 105, 1 ≤ m ≤ 105, − 106 ≤ x ≤ 106
answer：If there is no answer, please comment