题目描述

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

$\red 1$、“1 x y”，查询区间 $\red{[x,y]}$ 中的最大连续子段和，即 $\red{maxx\le l\le r\le y}$ $\red{{\sum i=lrA[i]}}$。

$\red 2$、“2 x y”，把 $\red{A[x]}$ 改成 $\red y$。

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

输入格式

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

第二行 $\red N$ 个整数 $\red{A[i]}$。

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

输出格式

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

每个答案占一行。

样例

输入样例

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

输出样例

2
-1

提示

$\red{N\le 500000}$,

$\red{M\le 100000}$