说明

有 $n$ 个格子，从左到右放成一排，编号为 $1-n$。共有 $m$ 次操作，有 $3$ 种操作类型：

1.修改一个格子的权值。

2.求连续一段格子权值和。

3.求连续一段格子的最大值。

对于每个2、3操作输出你所求出的结果。

输入格式

第一行2个整数 $n,m$。接下来一行 $n$ 个整数表示 $n$ 个格子的初始权值。

接下来 $m$ 行，每行3个整数 $p,x,y$，$p$ 表示操作类型，$p=1$ 时表示修改格子 $x$ 的权值为y，$p=2$ 时表示求区间 $[x,y]$ 内格子权值和，$p=3$ 时表示求区间$[x,y]$内格子最大的权值。

输出格式

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

样例

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

6
3

提示

HINT:时间限制：1.0s 内存限制：256.0MB

对于20%的数据n <= 100，m <= 200。

对于50%的数据n <= 5000，m <= 5000。

对于100%的数据1 <= n <= 100000，m <= 100000，0 <= 格子权值 <= 10000。