该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目背景

昆明的上午。

题目描述

atzk、 wqsing、 sad 在昆明打铁之后闲着没事正在打牌。

游戏规则是这样的：

给你一个长度为 $n$ 的牌序列，每张牌有一个值 $v_i$ 。

有两种操作：

• $1\ x\ v$ 表示将位置 $x$ 的值修改为 $v$。
• $2\ l\ r$ 表示询问区间 $a_l,a_{l + 1}...a_r$ 的所有"子区间和"的最大值，允许空区间，如 $[-1, -3,-2]$ 可得答案为 $0$。

输入格式

第一行两个整数 $n$, $m$。

第二行 $n$ 个整数，表示初始牌序列。

接下来 $m$ 行，表示 $m$ 种操作 $1\ x\ v\ /\ 2\ l\ r$。

输出格式

对于每一个询问，一行输出一个值，表示答案。

样例 #1

样例输入 #1

10 5
-1 1 5 3 4 -9 -9 -6 -10 -9 
2 3 7
2 3 6
1 10 -4
1 8 -4
1 9 -2

样例输出 #1

12
12

样例 #2

样例输入 #2

10 5
-6 -10 3 4 1 0 7 -2 -2 -2 
1 2 5
1 1 -9
1 7 -9
1 9 10
2 3 6

样例输出 #2

8

样例 #3

样例输入 #3

10 5
-10 -10 -9 3 -8 5 -3 1 -8 -7 
2 1 4
1 2 8
1 4 9
2 1 5
1 5 9

样例输出 #3

3
9

数据范围

$-10^9 \le v_i, v \le 10^9$

$1 \le x \le n \le 10^6, \ 1 \le m \le 10^6$

$1 \le l \le r \le n$