题目描述

这天，小P拿到了一个数列。

小P想要维护这个长度为 $n$ 的整数序列 $a_1, a_2, \ldots, a_n$，并支持以下两种操作：

• 0 i val：把 $a_i$ 修改为 $val$；
• 1 l r k：在 $a_l, a_{l+1}, \ldots, a_r$ 中选出至多 $k$ 个互不相交的子段，使得这些子段中所有元素之和最大，输出这个最大值。

形式化地，你需要选择若干整数对 $(x_1, y_1), (x_2, y_2), \ldots, (x_t, y_t)$，满足

$$l \le x_1 \le y_1 < x_2 \le y_2 < \cdots < x_t \le y_t \le r, \qquad t \le k$$

并最大化

$$a_{x_1} + a_{x_1+1} + \cdots + a_{y_1} + a_{x_2} + a_{x_2+1} + \cdots + a_{y_2} + \cdots + a_{x_t} + a_{x_t+1} + \cdots + a_{y_t}$$

注意 $t$ 可以取 $0$，此时所选元素之和记为 $0$。也就是说，答案不会小于 $0$。

输入格式

输入的第一行包含一个整数 $n$，表示序列的长度。

第二行包含 $n$ 个整数，依次表示 $a_1, a_2, \ldots, a_n$。

第三行包含一个整数 $m$，表示操作的个数。

接下来 $m$ 行，每行描述一次操作，格式为下列两种之一：

• 0 i val，表示把 $a_i$ 修改为 $val$；
• 1 l r k，表示一次询问。

输出格式

对于每一次 1 l r k 询问，输出一行一个整数，表示对应询问的答案。

请按照询问在输入中出现的顺序依次输出。

输入输出样例 #1

输入 #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

输入 #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, 9)$，元素之和为 $17$。
• 第二次询问选择子段 $(1, 7)$ 与 $(9, 9)$，元素之和为 $25$。

注意选择 $(1, 3)$ 与 $(7, 9)$ 只能得到 $20$，并不是最优解。

• 第三次询问的区间内所有元素都是负数，因此选择 $0$ 个子段，答案为 $0$。

数据范围

• 对于 $100\%$ 的数据，$1 \le n \le 10^5$，$1 \le m \le 10^5$，$1 \le i \le n$，$1 \le l \le r \le n$，$|a_i| \le 500$，$|val| \le 500$。数据保证所有询问的 $k$ 之和不超过 $2 \times 10^5$。