SD

Task

SD is one of the subjects taught in the first semester at UAIC-FII.

During the first seminar of this subject, the professor introduced the classic problem "Maximum Subarray Sum" to group 1A1. Naturally, everyone proposed different solutions, but two students found it interesting to present the following problem for you to solve:

We define a circular array as an array where the last element is considered adjacent to the first, allowing continuous traversal without a defined endpoint.

Given an array $A$ with $N$ elements, indexed from $1$ to $N$, and $Q$ operations of two types:

• Update: For an index $i$ $(1 \leq i \leq N)$ and a number $X$, the number at position $i$ is updated to $X$ $(A_i=X)$.
• Query: For two indices $St$ and $Dr$ $(1 \leq St \leq Dr \leq N)$, considering the subarray of $A$ between indices $St$ and $Dr$ as a circular array, determine the maximum sum of any non-empty subarray in that subarray.

Input data

The first line contains the numbers $N$ and $Q$.

The second line contains the $N$ numbers of array $A$.

The next $Q$ lines describe the operations as follows:

Each line contains three numbers:

• The first number is either $1$ or $2$, depending on the type of operation.
• If the first number is $1$, the operation is an update, followed by numbers $i$ and $X$ as described in the statement.
• If the first number is $2$, the operation is a query, followed by numbers $St$ and $Dr$ as described in the statement.

The values on the same line are space separated.

Output data

The output contains the maximum sums determined for each query operation, in the order given in the input, each on a separate line.

Constraints and clarifications

• $1 \leq N, Q \leq 300 \ 000$
• $1 \leq i, St, Dr \leq N$
• $-10^9\leq A_i, X\leq 10^9, (1 \leq i \leq N)$

Example

stdin

12 7
1 -5 2 3 4 -2 5 6 11 -1 15 -2
2 12 12
1 4 5
2 1 5
2 3 8
1 6 2
2 3 8
2 9 12

stdout

-2
12
22
24
25