爱画画的小Σ（draw）

题目背景

小$Σ$来到了小$π$的家里，又发现了小$π$画的画，只不过这幅画是一个长条，于是又拿起画笔在他的画上涂涂改改。

题目描述

这幅画有 $n$ 个片段，小$Σ$有 $m$ 次操作。一开始小$Σ$给这幅画的每个片段评了一个美观度，每次修改会选择第 $p$ 个片段把美观度修改成 $s$ ,或者问你在第 $x$ 个片段到第 $y$ 个片段中一些连续的片段美观值的和的最大值（包括 $x,y$ 两个片段）。

输入格式

第一行，两个整数 $n$ 和 $m$。

接下来一行，共有 $n$ 个整数,依次给出小$Σ$对每个片段的评价

接下来 $m$行 ，其中第一个整数 $k$ 为 $1$ 或 $2$。

• $k=1$ 表示，小$Σ$要评价画，接下来的两个整数 $x$ 和 $y$ 给出了选择片段的范围 $(1 \le x,y \le n)$。测试数据可能会出现 $x > y$ 的情况，需要进行交换；
• $k=2$ 表示，小$Σ$改变了对某个片段的打分，接下来的两个整数 $p$ 和 $s$，表示小$Σ$对第 $p$ 个片段的打分变成了 $s(1\le p\le N)$。

输出格式

小$Σ$每评价一次画，都对应输出一行，只包含一个整数，表示小$Σ$可以选出的美观值和的最大值。

样例 #1

样例输入 #1

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

样例输出 #1

2
-1

提示

对于 $100\%$ 的数据，$1 \le n \le 5 \times 10^5$，$1 \le m \le 10^5$，所有美观值都是绝对值不超过 $1000$ 的整数。