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

问题描述

给定 $n$ 个数 $a_1, a_2, a_3, \dots, a_n$。

支持 $q$ 个操作：

1. 修改操作：1 x d，将 $a_x$ 修改为$d$。
2. 查询操作：2 l r，查询区间 $[l, r]$ 内的最大子段和。

输入格式

• 第一行包含两个整数 $n, q$（$1 \leq n, q \leq 2 \times 10^5$）。
• 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$-10^9 \leq a_i \leq 10^9$）。
• 接下来的$q$ 行，每行表示一个操作，格式如下：
  • 1 x d（$1 \leq x \leq n, -10^9 \leq d \leq 10^9$）：修改$a_x$ 为$d$。
  • 2 l r（$1 \leq l \leq r \leq n$）：查询区间 $[l, r]$ 的最大子段和。

输出格式

对于每个查询操作，输出一行，表示查询的最大子段和。

样例输入

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

样例输出

4
5
4
-3