Segment Tree 2

Problem Description

You are given $n$ numbers $a_1, a_2, a_3, \dots, a_n$.

Support $q$ operations:

1. 1 x d: set $a_x = d$.
2. 2 l r: query the maximum subarray sum in $[l, r]$, i.e. find $l\leq l'\leq r' \leq r$ that maximizes $\sum_{i=l'}^{r'} a_i$.

Input Format

The first line contains two integers $n, q$ ($1\leq n, q\leq 2 \times 10^5$).

The next line contains $n$ integers $a_1, a_2, \dots, a_n$ ($-10^9 \leq a_i\leq 10^9$).

The next $q$ lines each contain an operation of the form 1 x d or 2 l r, with $1\leq x\leq n, 1\leq l\leq r\leq n, -10^9\leq d\leq 10^9$ guaranteed.

Output Format

For each query, output one line containing the answer.

Sample Input

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

Sample Output

4
5
4