A8925 | k-Maximum Subsequence Sum

Consider integer sequence $a_{1},a_{2},...,a_{n}$ . You should run queries of two types:

- The query format is " $0$ $i$ $val$ ". In reply to this query you should make the following assignment: $a_{i}=val$ .
- The query format is " $1$ $l$ $r$ $k$ ". In reply to this query you should print the maximum sum of at most $k$ non-intersecting subsegments of sequence $a_{l},a_{l+1},...,a_{r}$ . Formally, you should choose at most $k$ pairs of integers $(x_{1},y_{1}),(x_{2},y_{2}),...,(x_{t},y_{t})$ $(l<=x_{1}<=y_{1}<x_{2}<=y_{2}<...<x_{t}<=y_{t}<=r; t<=k)$ such that the sum $a_{x1}+a_{x1}+1+...+a_{y1}+a_{x2}+a_{x2}+1+...+a_{y2}+...+a_{xt}+a_{xt}+1+...+a_{yt}$ is as large as possible. Note that you should choose at most $k$ subsegments. Particularly, you can choose 0 subsegments. In this case the described sum considered equal to zero.

The first line contains integer $n$ $(1<=n<=10^{5})$ , showing how many numbers the sequence has. The next line contains $n$ integers $a_{1},a_{2},...,a_{n}$ $(|a_{i}|<=500)$ .

The third line contains integer $m$ $(1<=m<=10^{5})$ — the number of queries. The next $m$ lines contain the queries in the format, given in the statement.

All changing queries fit into limits: $1<=i<=n$ , $|val|<=500$ .

All queries to count the maximum sum of at most $k$ non-intersecting subsegments fit into limits: $1<=l<=r<=n$ , $1<=k<=20$ . It is guaranteed that the number of the queries to count the maximum sum of at most $k$ non-intersecting subsegments doesn't exceed $10000$ .

For each query to count the maximum sum of at most $k$ non-intersecting subsegments print the reply — the maximum sum. Print the answers to the queries in the order, in which the queries follow in the input.