J. Johannes Loves Games
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Lieutenant Johannes and Hamilton are one of the most well decorated math students in their entire country! They somewhat enjoy discussing very particular algorithms with each other, and on one fine Wednesday afternoon, they decided to play some nerdy game. It goes like this: Lieutenant Johannes gives Hamilton an array and decides to ask a couple of questions about it. Each question has a similar structure; he asks Hamilton to figure out the value of the largest subarray sum of some particular range that he chooses of the original array. Seems easy, doesn't it? In order to challenge Hamilton even further, in between questions, he'll remember that the original array is a bit different and modifies a certain element within it.

However, recently Hamilton has been feeling very sick and so isn't able to think very straight, so he asks you to think for him as these types of games, in his opinion, are too trivial to expend energy thinking about.

Input

The first line of the input contains two integers, $$$n$$$ and $$$q$$$, $$$(1 \leq n \leq 10^6)$$$, $$$(1 \leq q \leq 10^6)$$$ — the size of the array and the amount of questions Johannes asks.

The second line contains $$$n$$$ integers $$$(a_1, a_2, ..., a_n)$$$ $$$(-10^{12} \leq a_i \leq 10^{12})$$$ — the elements that Johannes gives to you.

The next $$$q$$$ lines will contain information about the $$$i^{th}$$$ question done by Johannes. Each line will start with an integer $$$t_i$$$, $$$(1 \leq t_i \leq 2)$$$ — the type of query.

  • For $$$t_i = 1$$$, 2 integers, $$$p$$$ and $$$x$$$, $$$(1 \leq p \leq n)$$$, $$$(-10^{12} \leq x \leq 10^{12})$$$ — the position where Johannes modifies the array and the value that replaces it.
  • For $$$t_i = 2$$$, 2 integers, $$$l$$$ and $$$r$$$, $$$(1 \leq l \leq r \leq n)$$$ — the range in which Johannes wants to figure out what is the largest subarray sum within it. It is guaranteed that there's at least one query of this type.
Output

For every query in which $$$t_i = 2$$$, print out the largest subarray sum in the range $$$[l, r]$$$.

Example
Input
7 3
17 9 4 -2 0 -12 38
2 3 7
1 5 3
2 2 6
Output
38
14