Description

有$n$个格子，从左到右放成一排，编号为$1-n$。 共有$m$次操作，有$3$种操作类型：
$1.$修改一个格子的权值
$2.$求连续一段格子权值和
$3.$求连续一段格子的最大值。 对于每个$2、3$操作输出你所求出的结果。

Format

Input

第一行$2$个整数$n，m。$
接下来一行$n$个整数表示$n$个格子的初始权值。 接下来$m$行，每行$3$个整数$p,x,y，$ $p$表示操作类型 $p=1$时表示修改格子$x$的权值为$y$
$p=2$时表示求区间$[x,y]$内格子权值和
$p=3$时表示求区间$[x,y]$内格子最大的权值
(对于$20$的数据$n < = 100，m < = 200。$
对于$50$的数据$n < = 5000，m < = 5000。$
对于$100$的数据$1 < = n < = 100000，m < = 100000，0 < = 格子权值 < = 10000。)$

Output

有若干行，行数等于$p=2$或$3$的操作总数。 每行$1$个整数，对应了每个$p=2$或$3$操作的结果。

Samples

4 3
1 2 3 4
2 1 3
1 4 3
3 1 4 

6
3