题目描述

给定长度为 $N$ 的数列 $A$，以及 $M$ 条指令，每条指令可能是以下两种之一：

$1$ $x$ $y$:查询区间 $[x,y]$ 中的最大连续子段和

$2$ $x$ $y$:把 $A[x]$ 改成 $y$

输入描述

第一行两个整数 $N$,$M$。

第二行 $N$ 个整数 $A[i]$。

接下来 $M$ 行每行 $3$ 个整数 $k$,$x$,$y$，$k=1$ 表示查询（此时如果 $x>y$，请交换 $x$,$y$），$k=2$ 表示修改。

$N≤500000,M≤100000$,

$−1000≤A[i]≤1000$

输出描述

对于每个查询指令输出一个整数表示答案。

每个答案占一行。

样例

样例输入#1

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

样例输出#1

2
-1

样例输入#2

5 5
847 479 469 117 334 
1 2 5
2 5 -936
2 3 -427
1 2 4
2 2 686

样例输出#2

1399
479