D. k-最大子段和
时间限制：每个测试点 $4$ 秒
内存限制：$256$ 兆字节

考虑一个整数序列 $a_1, a_2, \dots, a_n$。你需要执行两种类型的查询：

• 查询格式为 0 i val。作为回复，你需要进行如下赋值：$a_i := val$。
• 查询格式为 1 l r k。作为回复，你需要输出序列 $a_l, a_{l+1}, \dots, a_r$ 中至多 $k$ 个不相交子段的最大和。形式化地，你需要选择至多 $k$ 对整数 $(x_1, y_1), (x_2, y_2), \dots, (x_t, y_t)$，满足：

$$l \le x_1 \le y_1 < x_2 \le y_2 < \dots < x_t \le y_t \le r,\quad t \le k $$

使得下面的和最大：

$$\sum_{j=1}^t \sum_{p = x_j}^{y_j} a_p$$

注意：你可以选择 $0$ 个子段，此时和视为 $0$。

---

输入格式
第一行包含整数 $n$（$1 \le n \le 10^5$）——序列的长度。
第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$|a_i| \le 500$）。
第三行包含整数 $m$（$1 \le m \le 10^5$）——查询的数量。
接下来的 $m$ 行，每行包含一个查询，格式如上所述。

所有修改查询满足：$1 \le i \le n$，$|val| \le 500$。
所有求至多 $k$ 个不相交子段最大和的查询满足：$1 \le l \le r \le n$，$1 \le k \le 20$。
保证求最大子段和的查询数量不超过 $10000$。

---

输出格式
对于每个求最大子段和的查询，输出一行一个整数——最大和。按照查询在输入中出现的顺序输出。

---

样例输入 1

9
9 -8 9 -1 -1 -1 9 -8 9
3
1 1 9 1
1 1 9 2
1 4 6 3

样例输出 1

17
25
0

样例输入 2

15
-4 8 -3 -10 10 4 -7 -7 0 -6 3 8 -10 7 2
15
1 3 9 2
1 6 12 1
0 6 5
0 10 -7
1 4 9 1
1 7 9 1
0 10 -3
1 4 10 2
1 3 13 2
1 4 11 2
0 15 -9
0 13 -9
0 11 -10
1 5 14 2
1 6 12 1

样例输出 2

14
11
15
0
15
26
18
23
8

---

样例 1 解释

• 第一个查询：可以选择一个子段 $(1, 9)$，和为 $17$。
• 第二个查询：最优选择是 $(1, 7)$ 和 $(9, 9)$，和为 $25$。
• 第三个查询：区间内全为负数，所以选择 $0$ 个子段，和为 $0$。