Optimal Travel Path

OIVillage is a picturesque village that has recently built a railroad connecting its n most famous scenic spots. The railway always starts at station 1 and proceeds in order through the scenic spots. Each scenic spot i is assigned a beauty value \(a_i\). A journey from station 1 to station \(j\) has a value equal to the sum of the beauties of the stops visited, i.e. \(P(j)=\sum_{i=1}^{j}a_i\). Due to changes in weather and season, the beauty value of a scenic spot may change over time.

There are two types of operations:

• Update operation: Change the beauty value of a specific scenic spot.
• Query operation: Given an interval \([L,R]\), choose a station \(j\) with \(L\le j\le R\) so that \(P(j)\) is maximized, and report that maximum value.

You are given the initial beauty values for the n scenic spots and q operations. Help xkszltl to provide the best travel guidance by handling these operations efficiently.

Note: After an update operation at station x (changing \(a_x\) to a new value \(y\)), all prefix sums \(P(j)\) for \(j \ge x\) will change accordingly.

inputFormat

The first line contains two integers n and q (\(1\le n,q\le 10^5\)), representing the number of scenic spots and the number of operations respectively.

The second line contains n integers \(a_1,a_2,\dots,a_n\) (\(|a_i|\le 10^9\)) indicating the initial beauty values of the scenic spots.

The following q lines each describe an operation. An operation is in one of the following two formats:

• 1 x y: Update the beauty value at station x to y (i.e. set \(a_x=y\)).
• 2 L R: Query and output the maximum journey value \(P(j)\) among stations \(j\) where \(L\le j\le R\).

It is guaranteed that there is at least one query operation.

outputFormat

For each query operation (type 2), output one line containing a single integer — the maximum journey value in the specified station interval.

sample

5 5
1 2 3 4 5
2 1 3
1 3 10
2 2 5
1 1 -5
2 1 5

6
22
16