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 of
queries, 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
For all points and
For additional points:
The first line contains , and .
The next lines contain 3 integers, representing a query.
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
15 23 19
, yielding a match value of .
After the updates, he will choose the interval , to get a value of .
The final query can only start on positions or , therefore can only cover .