== include(page="template/taskheader" task_id="panamasum") ==

Poveste şi cerinţă...

While their car was lost in Panama, Carlos and Pablo decided to have fun with some math. One day, Carlos came up with what he called a Panama sum.
 
Basically, a Panama sum is the sum of some values in an $1$-indexed array, where the values on the odd positions are added to the sum and the values on the even positions are subtracted from the sum.
 
For example, the Panama sum of the array [$10, 6, 9, 4, 2, 0$] is $10$ - $6$ + $9$ - $4$ + $2$ - $0$ which is equal to $11$
 
Because finding this is way too easy for Pablo (he is a programmer), he decided to make this challenge more difficult.
 
Therefore, he invented the maximum Panama sum, which is defined as the maximum Panama sum we can get if we select a non-empty subarray from a given array.
 
Now he wants Carlos to find this value for multiple queries which might involve changing some values as well.
 
Help Carlos get this problem done and he will take you for a ride once he finds his car!

h2. Date de intrare

Fişierul de intrare $panamasum.in$ ...

The first line of the input file $panamasum.in$ consists of two integers, $n$ and $q$.
 
The second line of the input consists of $n$ integers, representing the initial array $v$.
 
The next $q$ lines of the input contain the queries you are given.
 
On each line, you will get the description of a query, which can be of two types:
 
$1$ $a$ $b$ - the value on position $a$ is changed to $b$.
 
$2$ $l$ $r$ - find the maximum Panama sum of the subarray [$l, r$].

h2. Date de ieşire

În fişierul de ieşire $panamasum.out$ ...

The output file $panamasum.out$ will contain as many lines as queries of type $2$ exist in the input (there is at least one query of type $2$). Each line will contain the answer to a query, in the order they were given in the input.

h2. Restricţii

* $... ≤ ... ≤ ...$

* $1 ≤ n, q ≤ 10^5$
* $0 ≤ v[i], b ≤ 10^9$
* For tests worth $20$ points, $1 ≤ n ≤ 100$, $1 ≤ q ≤ 1000$.
* For tests worth $20$ more points, $1 ≤ n ≤ 5000$, $1 ≤ q ≤ 5000$.

h2. Exemplu
table(example). |_. panamasum.in |_. panamasum.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 10 6
5 9 1 2 3 4 6 4 2 8
2 3 7
2 4 10
2 6 9
1 5 8
2 1 10
2 4 6
| 6
10
6
10
8

|

h3. Explicaţie
 
...

== include(page="template/taskfooter" task_id="panamasum") ==