Amestris generals along with his sniper rifle. Unfortunately, he can't tell which one is Fuhrer King Bradley. He has assigned each general a matching value, representative of how much that general is similar to Bradley. Initially, the matching value of each general is . His rifle only has a single bullet, but that bullet has a penetrating power of . This means that when he shoots, he can kill consecutive generals in the line. would like the sum of matching values inside this range to be high as possible.

has sneaked into a meeting ofqueries, each in one of forms:

will have`0 P V`

: the general at position increases by value`1 L R`

: would like to know the highest possible kill he can achieve if the first(leftmost) person killed is between position and

#### Subtasks

For all points: and

For points:

For additional points:

#### Input Specification

The first line contains , and .

The next lines contain 3 integers, representing a query.

Note that .

#### Sample Input

```
8 4 8
0 2 10
0 0 4
0 6 15
1 0 5
0 3 6
0 1 3
1 0 7
1 1 2
```

#### Sample Output

```
15
23
19
```

#### Explanation

, , and , yielding a match value of .

After the updates, he will choose the interval , , and , to get a value of .

The final query can only start on positions or , therefore can only cover .

## Comments

wait how can but in the sample input and in the 2nd line

isnt ? whats the problem?

I believe he meant to say in the 2nd line of input, .

This would imply there are positions in the array.

It is technically correct mind you, but it would be easier if the constraints were more clear.

https://dmoj.ca/submission/862887

If I am not mistaken there is a case where .

However, the sample case seems to imply that the array is 0-indexed.

I am really confused with this problem.

For instance, how can and be complex numbers if they are positions?

Is greater than or equal than (since the sample input does not confirm that)?

Can be both and , since there are only guard positions?

And just to double check, the guards are in a line, right?

Thank you for all your help!

Edit: nvm, fixed

Constraints have be changed to

Wait, as in complex numbers?

Note that the problem setter is an amateur and did not mention that and could be .

This comment is hidden due to too much negative feedback. Show it anyway.