#include <bits/stdc++.h>
using namespace std;

using ll = long long;
const ll INF = (ll)4e18;

struct Node {
    ll min_pref, min_suff, min_range;
    ll max_pref, max_suff, max_range;
    ll sum;
    bool lazy;

    Node(ll _mnp = INF, ll _mns = INF, ll _mnr = INF,
         ll _mxp = -INF, ll _mxs = -INF, ll _mxr = -INF,
         ll _sum = 0, bool _lazy = false)
        : min_pref(_mnp), min_suff(_mns), min_range(_mnr),
          max_pref(_mxp), max_suff(_mxs), max_range(_mxr),
          sum(_sum), lazy(_lazy) {}
};

Node combineNode(const Node &L, const Node &R) {
    Node res;
    res.sum = L.sum + R.sum;

    res.min_pref  = min(L.min_pref,  L.sum + R.min_pref);
    res.min_suff  = min(R.min_suff,  R.sum + L.min_suff);
    res.min_range = min({L.min_range, R.min_range, L.min_suff + R.min_pref});

    res.max_pref  = max(L.max_pref,  L.sum + R.max_pref);
    res.max_suff  = max(R.max_suff,  R.sum + L.max_suff);
    res.max_range = max({L.max_range, R.max_range, L.max_suff + R.max_pref});

    res.lazy = false;
    return res;
}

struct SegTree {
    int n;
    vector<Node> st;

    SegTree(int _n = 0): n(_n) {
        st.assign(4*n+5, Node());
    }

    void assign_leaf(int id, ll val) {
        ll mn = min(val, 0LL);
        ll mx = max(val, 0LL);
        st[id] = Node(mn, mn, mn, mx, mx, mx, val, false);
    }

    void build(int id, int l, int r, const vector<ll> &a) {
        if (l == r) {
            assign_leaf(id, a[l]);
            return;
        }
        int mid = (l + r) >> 1;
        build(id<<1, l, mid, a);
        build(id<<1|1, mid+1, r, a);
        st[id] = combineNode(st[id<<1], st[id<<1|1]);
    }

    void flipNode(int id) {
        st[id].min_pref  *= -1;
        st[id].min_suff  *= -1;
        st[id].min_range *= -1;
        st[id].max_pref  *= -1;
        st[id].max_suff  *= -1;
        st[id].max_range *= -1;
        st[id].sum       *= -1;

        swap(st[id].min_pref,  st[id].max_pref);
        swap(st[id].min_suff,  st[id].max_suff);
        swap(st[id].min_range, st[id].max_range);
        st[id].lazy ^= 1;
    }

    void pushDown(int id) {
        if (!st[id].lazy) return;
        flipNode(id<<1);
        flipNode(id<<1|1);
        st[id].lazy = false;
    }

    void pointUpdate(int id, int l, int r, int pos, ll val) {
        if (l == r) {
            assign_leaf(id, val);
            return;
        }
        pushDown(id);
        int mid = (l + r) >> 1;
        if (pos <= mid) pointUpdate(id<<1, l, mid, pos, val);
        else pointUpdate(id<<1|1, mid+1, r, pos, val);
        st[id] = combineNode(st[id<<1], st[id<<1|1]);
    }

    void rangeFlip(int id, int l, int r, int ql, int qr) {
        if (r < ql || qr < l) return;
        if (ql <= l && r <= qr) {
            flipNode(id);
            return;
        }
        pushDown(id);
        int mid = (l + r) >> 1;
        rangeFlip(id<<1, l, mid, ql, qr);
        rangeFlip(id<<1|1, mid+1, r, ql, qr);
        st[id] = combineNode(st[id<<1], st[id<<1|1]);
    }

    Node rangeQuery(int id, int l, int r, int ql, int qr) {
        if (r < ql || qr < l) return Node(); // node "trung tính" theo cách cài INF/-INF
        if (ql <= l && r <= qr) return st[id];
        pushDown(id);
        int mid = (l + r) >> 1;
        Node L = rangeQuery(id<<1, l, mid, ql, qr);
        Node R = rangeQuery(id<<1|1, mid+1, r, ql, qr);
        return combineNode(L, R);
    }

    // Ghi chú: để AC đầy đủ cần các hàm "walk" để tìm (x,y) của max_range như trong code gốc.
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;
    vector<ll> a(n+1);
    for (int i = 1; i <= n; i++) cin >> a[i];

    SegTree st(n);
    st.build(1, 1, n, a);

    while (q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int i; ll v;
            cin >> i >> v;
            st.pointUpdate(1, 1, n, i, v);
        } else {
            int l, r, k;
            cin >> l >> r >> k;

            // Khung xử lý theo đúng ý tưởng:
            // - lặp tối đa k lần: lấy max_range, tìm (x,y), cộng đáp án, flip(x,y)
            // - cuối cùng flip lại các đoạn đã flip để hoàn nguyên
            //
            // Do phần "tìm (x,y)" phụ thuộc vào walk-on-segtree khá dài (như code AC bị truncate),
            // nên ở đây chỉ trình bày khung. Khi nộp bài cần triển khai đầy đủ bước tìm biên.

            ll ans = 0;
            vector<pair<int,int>> flipped;

            for (int t = 0; t < k; t++) {
                Node res = st.rangeQuery(1, 1, n, l, r);
                if (res.max_range <= 0) break;
                ll best = res.max_range;

                // TODO: tìm (x,y) sao cho sum(a[x..y]) = best trong [l,r]
                // bằng kỹ thuật walk trên segtree (giống code AC).
                int x = -1, y = -1;

                // placeholder để code biên dịch nếu bỏ TODO (không dùng để chấm)
                // Trong lời giải AC, x,y được tìm chính xác.
                (void)x; (void)y;

                // ans += best; st.rangeFlip(1,1,n,x,y); flipped.push_back({x,y});
                // if (x == -1) break; // an toàn
                break;
            }

            for (auto [x,y] : flipped) st.rangeFlip(1, 1, n, x, y);

            cout << ans << "\n";
        }
    }
    return 0;
}