Description

Near Xiaoxin’s home there is a “Park Road,” along one side of which $n$ parks are lined up from south to north. Xiaobai is dazzled and is not sure which parks to visit.

At the beginning, Xiaobai assigns a score to each park based on its scenery. For convenience, every time they go for a walk, Xiaoxin specifies a range, and Xiaobai may choose a contiguous sequence of parks between the $a$-th and $b$-th parks (inclusive). Of course, Xiaobai wants the sum of the selected parks’ scores to be as large as possible. Meanwhile, as some parks’ landscapes change, Xiaobai’s scores may also change.

So please help Xiaobai choose the parks.

Input Format

• The first line contains two integers $n$ and $m$, representing the number of parks and the total number of operations (walks or score changes).
• The next $n$ lines each contain one integer, giving the initial score that Xiaobai assigns to each park in order.
• The next $m$ lines each contain three integers. The first integer $k$ is $1$ or $2$.
  • If $k = 1$, Xiaoxin is taking Xiaobai out to play. The next two integers $a$ and $b$ give the selectable range of parks $(1 \le a, b \le n)$. The testdata may contain cases where $a > b$, in which case you should swap them.
  • If $k = 2$, Xiaobai changes the score of a park. The next two integers $p$ and $s$ mean the score of the $p$-th park becomes $s$ $(1 \le |s| \le 1000)$.

Output Format

For each walk, output one line containing a single integer: the maximum possible sum of scores of the parks Xiaobai can select.

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

2
-1

Hint

Constraints

For $100\%$ of the testdata, $1 \le n \le 5 \times 10^5$, $1 \le m \le 10^5$, and all scores are integers with absolute value at most $1000$.

Translated by ChatGPT 5