题目描述

圆滑博士喜欢研究数列问题。这次，他面对的是一个长为 $n$ 的整数数列 $a_1, a_2, \dots, a_n$。

圆滑博士定义了一个函数 $f(l, r)$，表示区间 $[l, r]$ 中的最大子段和。形式化地，给定整数 $l$ 和 $r$ $(1 \leq l \leq r \leq n)$，$f(l, r)$ 被定义为：

$$f(l, r) = \max\limits_{l \leq i \leq j \leq r} \left( \sum\limits_{k=i}^{j} a_k \right)$$

现在圆滑博士会给出 $q$条指令，每条指令可能是以下两种之一：

1 x y，查询 $f(x, y)$。

2 x y，把 $a_x$修改为 $y$。

你需要执行圆滑博士的指令，并帮圆滑博士回答查询任务。

输入格式

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

第二行 $n$ 个整数 $a_i(-1000\leq a_i \leq 1000)$。

接下来 $q$ 行每行 3 个整数 $k, x, y$：

$k=1$ 表示查询 $f(x, y)$（此时如果 $x>y$，请交换 $x,y$）；

$k=2$ 表示修改, 即把 $a_x$修改为 $y$。

输出格式

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

样例

5 5
-809 672 208 -145 -63
2 1 619
1 3 2
2 3 255
1 3 3
2 4 -296

880
255

数据范围

对于 $40\%$ 的数据满足 $n\leq 1000, q \leq 1000$。

对于 $100\%$ 的数据满足 $n \leq 3 \times 10^5, q \leq 3 \times 10^5$。