题目描述

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

• 查询操作：1 x y
  查询区间 $[x, y]$ 中的最大连续子段和，即：

  $$\max_{x \leq i \leq j \leq y} \left( \sum_{k=i}^{j} A[k] \right)$$

• 修改操作：2 x y
  将 $A[x]$ 的值改为 $y$。

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

输入格式

• 第一行包含两个整数 $N$ 和 $M$，分别表示数组长度和操作次数。
• 第二行包含 $N$ 个整数，表示初始数组 $A[1..N]$。
• 接下来 $M$ 行，每行三个整数 $k, x, y$：
  • 若 $k = 1$，表示查询操作；
  • 若 $k = 2$，表示修改操作；
  • 如果 $x > y$，请交换 $x$ 和 $y$。

输出格式

对于每一个查询操作，输出一个整数表示该区间内最大连续子段和。每个答案占一行。

样例输入

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

样例输出

2
-1

数据范围

• $1 \leq N \leq 500000$
• $1 \leq M \leq 100000$
• $-1000 \leq A[i] \leq 1000$