Consider integer sequence *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub>. 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*<sub class="lower-index">*i*</sub> = *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*<sub class="lower-index">*l*</sub>, *a*<sub class="lower-index">*l* + 1</sub>, ..., *a*<sub class="lower-index">*r*</sub>. Formally, you should choose at most *k* pairs of integers (*x*<sub class="lower-index">1</sub>, *y*<sub class="lower-index">1</sub>), (*x*<sub class="lower-index">2</sub>, *y*<sub class="lower-index">2</sub>), ..., (*x*<sub class="lower-index">*t*</sub>, *y*<sub class="lower-index">*t*</sub>) (*l* ≤ *x*<sub class="lower-index">1</sub> ≤ *y*<sub class="lower-index">1</sub> &lt; *x*<sub class="lower-index">2</sub> ≤ *y*<sub class="lower-index">2</sub> &lt; ... &lt; *x*<sub class="lower-index">*t*</sub> ≤ *y*<sub class="lower-index">*t*</sub> ≤ *r*; *t* ≤ *k*) such that the sum *a*<sub class="lower-index">*x*<sub class="lower-index">1</sub></sub> + *a*<sub class="lower-index">*x*<sub class="lower-index">1</sub> + 1</sub> + ... + *a*<sub class="lower-index">*y*<sub class="lower-index">1</sub></sub> + *a*<sub class="lower-index">*x*<sub class="lower-index">2</sub></sub> + *a*<sub class="lower-index">*x*<sub class="lower-index">2</sub> + 1</sub> + ... + *a*<sub class="lower-index">*y*<sub class="lower-index">2</sub></sub> + ... + *a*<sub class="lower-index">*x*<sub class="lower-index">*t*</sub></sub> + *a*<sub class="lower-index">*x*<sub class="lower-index">*t*</sub> + 1</sub> + ... + *a*<sub class="lower-index">*y*<sub class="lower-index">*t*</sub></sub> 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<sup class="upper-index">5</sup>), showing how many numbers the sequence has. The next line contains *n* integers *a*<sub class="lower-index">1</sub>, *a*<sub class="lower-index">2</sub>, ..., *a*<sub class="lower-index">*n*</sub> (|*a*<sub class="lower-index">*i*</sub>| ≤ 500). 

The third line contains integer *m* (1 ≤ *m* ≤ 10<sup class="upper-index">5</sup>) — 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.
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100010;
const int INF = 0x3f3f3f3f;
typedef long long ll;
int N;
int arr[MAXN];
struct Node {
    // 0 -> normal max sum
    // 1 -> include left
    // 2 -> include right
    // 3 -> include left and right
    int s, sum[25][4];
    Node (){
        memset(sum, -INF, sizeof(sum));
        for (int i = 0; i < 4; i++) sum[0][i] = 0;
        s = 0;
    }
} ST[MAXN * 4];
Node comb (Node L, Node R){
    Node t;
    t.s = L.s + R.s;
    t.sum[1][3] = t.s;
    for (int i = 0; i <= 20; i++){
        for (int j = 0; j <= 20 && j + i <= 21; j++){
            t.sum[i][0] = max(t.sum[i][0], L.sum[j][0] + R.sum[i - j][0]);
            if (j != 0 && j != i) t.sum[i - 1][0] = max(t.sum[i - 1][0], L.sum[j][2] + R.sum[i - j][1]);
            if (j != 0){
                t.sum[i][1] = max(t.sum[i][1], L.sum[j][1] + R.sum[i - j][0]);
                if (i != 1) t.sum[i - 1][1] = max(t.sum[i - 1][1], L.sum[j][3] + R.sum[i - j][1]);
            }
            if (j != i){
                t.sum[i][2] = max(t.sum[i][2], L.sum[j][0] + R.sum[i - j][2]);
                if (i != 1) t.sum[i - 1][2] = max(t.sum[i - 1][2], L.sum[j][2] + R.sum[i - j][3]);
            }
            if (i != 1 && j != 0 && j != i) t.sum[i][3] = max(t.sum[i][3], L.sum[j][2] + R.sum[i - j][1]);
            if (i != 1) for (int k = 0; k < 4; k++) t.sum[i][k] = max(t.sum[i][k], t.sum[i - 1][k]);
        }
    }
    return t;
}
Node query (int l, int r, int node = 1, int tl = 1, int tr = N){
    if (l > r){
        Node t;
        return t;
    }
    if (l == tl && r == tr){
        return ST[node];
    }
    int tm = (tl + tr) >> 1;
    Node L = query(l, min(r, tm), node << 1, tl, tm);
    Node R = query(max(l, tm + 1), r, node << 1 | 1, tm + 1, tr);
    Node res = comb(L, R);
    return res;
}
void update (int idx, int val, int node = 1, int tl = 1, int tr = N){
    if (tl == tr){
        ST[node].s = val;
        for (int i = 0; i <= 20; i++){
            for (int j = 0; j < 4; j++){
                ST[node].sum[i][j] = (i == 0) ? 0 : val;
            }
        }
        return;
    }
    int tm = (tl + tr) >> 1;
    if (idx <= tm) update(idx, val, node << 1, tl, tm);
    else update(idx, val, node << 1 | 1, tm + 1, tr);
    ST[node] = comb(ST[node << 1], ST[node << 1 | 1]);
}
void build (int node = 1, int tl = 1, int tr = N){
    if (tl > tr) return;
    if (tl == tr){
        ST[node].s = arr[tl];
        for (int i = 0; i <= 20; i++){
            for (int j = 0; j < 4; j++){
                ST[node].sum[i][j] = (i == 0) ? 0 : arr[tl];
            }
        }
        return;
    }
    int tm = (tl + tr) >> 1;
    build(node << 1, tl, min(tm, tr));
    build(node << 1 | 1, max(tm + 1, tl), tr);
    ST[node] = comb(ST[node << 1], ST[node << 1 | 1]);
}
int main() {
    cin >> N;
    for (int i = 1; i <= N; i++){
        cin >> arr[i];
    }
    build();
    int Q;
    cin >> Q;
    while (Q--){
        int op;
        cin >> op;
        if (op == 0){
            int i, val;
            cin >> i >> val;
            arr[i] = val;
            update(i, val);
        }
        if (op == 1){
            int l, r, k;
            cin >> l >> r >> k;
            Node ans = query(l, r);
            cout << max(0, ans.sum[k][0]) << "\n";
        }
    }
}