Untitled

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

#ifdef LOCAL
#include "debug.h"
#else
#define debug(x...)
#endif

const long long CUT = LLONG_MIN / 2;

struct segtree {

    struct node {
        long long seg, pref, suf, sum;
    };

    node combine(node a, node b) {
        return {
            max({a.seg, b.seg, a.suf + b.pref}),
            max(a.pref, a.sum + b.pref),
            max(b.suf, b.sum + a.suf),
            a.sum + b.sum
        };
    }

    node one_element(long long x) {
        return {
            max(0LL, x),
            max(0LL, x),
            max(0LL, x),
            x
        };
    }

    const node ZERO = {0, 0, 0, 0};

    int size;
    vector<node> tree;

    void init(int n) {
        size = 1;
        while (size < n) size *= 2;
        tree.assign(2 * size - 1, ZERO);
    }

    void build(vector<long long> &a, int x, int lx, int rx) {
        if (rx - lx == 1) {
            if (lx < (int)a.size()) {
                tree[x] = one_element(a[lx]);
            }
        } else {
            int m = (lx + rx) / 2;
            build(a, x * 2 + 1, lx, m);
            build(a, x * 2 + 2, m, rx);
            tree[x] = combine(tree[x * 2 + 1], tree[x * 2 + 2]);
        }
    }

    void build(vector<long long> &a) {
        init(a.size() + 1);
        build(a, 0, 0, size);
    }

    node get(int l, int r, int x, int lx, int rx) {
        if (lx >= r || rx <= l) {
            return ZERO;
        } else if (lx >= l && rx <= r) {
            return tree[x];
        } else {
            int m = (lx + rx) / 2;
            return combine(get(l, r, x * 2 + 1, lx, m), get(l, r, x * 2 + 2, m, rx));
        }
    }

    long long get(int l, int r) {
        return get(l, r, 0, 0, size).seg;
    }

    void set(int i, long long v, int x, int lx, int rx) {
        if (rx - lx == 1) {
            tree[x] = one_element(v);
        } else {
            int m = (lx + rx) / 2;
            if (i < m) {
                set(i, v, x * 2 + 1, lx, m);
            } else {
                set(i, v, x * 2 + 2, m, rx);
            }
            tree[x] = combine(tree[x * 2 + 1], tree[x * 2 + 2]);
        }
    }

    void set(int i, long long v) {
        set(i, v, 0, 0, size);
    }

};

void solve() {
    int n, q;
    cin >> n >> q;
    vector<long long> a(n * 2 - 1);
    for (int i = 0; i < n * 2 - 1; i += 2) {
        cin >> a[i];
    }
    segtree tr;
    tr.build(a);
    while (q--) {
        int t;
        cin >> t;
        if (t == 1) {
            int i;
            cin >> i;
            tr.set((i - 1) * 2 + 1, CUT);
        } else if (t == 2) {
            int i;
            cin >> i;
            tr.set((i - 1) * 2 + 1, 0LL);
        } else {
            int l, r;
            cin >> l >> r;
            //debug(tr.tree[0].seg);
            cout << max(0LL, tr.get((l - 1) * 2, (r - 1) * 2 + 1)) << '\n';
        }
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int tests = 1;
    // cin >> tests;
    while (tests--) {
        solve();
    }
    return 0;
}