#include <bits/stdc++.h>

using namespace std;

namespace segTreee {
    template <typename U,
              typename V,
              typename W,
              class mergeClass,
              class addClass,
              class setClass>
    class segTree {
        private:
            int n;
            vector <U> t;
            vector <V> Sum;
            vector <W> Set;
            vector <bool> doSum;
            vector <bool> doSet;

            static inline int leSon(int i) { return 2 * i; }
            static inline int riSon(int i) { return 2 * i + 1; }

            inline void applySum(int i, V &__Sum) {
                t[i] = addClass()(t[i], __Sum);
                if (doSum[i] == false) Sum[i] = V :: NIL;
                Sum[i] = addClass()(Sum[i], __Sum);
            }

            inline void applySet(int i, W &__Set) {
                t[i] = setClass()(t[i], __Set);
                doSet[i] = true;
                Set[i] = __Set;
            }

            inline void pushSons(int i) {
                if (doSum[i] == true) {
                    applySum(leSon(i), Sum[i]);
                    applySum(riSon(i), Sum[i]);
                    doSum[i] = false;
                }
                if (doSet[i] == true) {
                    applySet(leSon(i), Set[i]);
                    applySet(riSon(i), Set[i]);
                    doSet[i] = false;
                }
            }

            void treeConstruct(int i, int le, int ri, vector <W> &initVal) {
                if (ri - le == 1) {
                    t[i] = setClass()(t[i], initVal[le]);
                    t[i].le = le;
                    t[i].ri = ri;
                }
                else {
                    int mi = (le + ri) / 2;
                    treeConstruct(leSon(i), le, mi, initVal);
                    treeConstruct(riSon(i), mi, ri, initVal);
                    t[i] = mergeClass()(t[leSon(i)], t[riSon(i)]);
                }
            }
        public:
            segTree(int __n) {
                n = __n;
                t = vector <U>(4 * n, U :: NIL);
                Set = vector <W>(4 * n, W :: NIL);
                Sum = vector <V>(4 * n, V :: NIL);
                doSum = doSet = vector <bool>(4 * n, false);
                vector <W> initVal(n, W :: NIL);
                treeConstruct(1, 0, n, initVal);
            }

            segTree(int __n, vector <W> initVal) {
                n = __n;
                t = vector <U>(4 * n, U :: NIL);
                Set = vector <W>(4 * n, W :: NIL);
                Sum = vector <V>(4 * n, V :: NIL);
                doSum = doSet = vector <bool>(4 * n, false);
                treeConstruct(1, 0, n, initVal);
            }

            void addSegment(int leQ, int riQ, V v, int i, int le, int ri) {
                if (leQ < ri && le < riQ) {
                    if (leQ <= le && ri <= riQ) {
                        applySum(i, v);
                    }
                    else {
                        pushSons(i);
                        int mi = (le + ri) / 2;
                        addSegment(leQ, riQ, v, leSon(i), le, mi);
                        addSegment(leQ, riQ, v, riSon(i), mi, ri);
                        t[i] = mergeClass()(t[leSon(i)], t[riSon(i)]);
                    }
                }
            }

            void setSegment(int leQ, int riQ, W v, int i, int le, int ri) {
                if (leQ < ri && le < riQ) {
                    if (leQ <= le && ri <= riQ) {
                        applySet(i, v);
                    }
                    else {
                        pushSons(i);
                        int mi = (le + ri) / 2;
                        setSegment(leQ, riQ, v, leSon(i), le, mi);
                        setSegment(leQ, riQ, v, riSon(i), mi, ri);
                        t[i] = mergeClass()(t[leSon(i)], t[riSon(i)]);
                    }
                }
            }

            U Query(int leQ, int riQ, int i, int le, int ri) {
                if (leQ < ri && le < riQ) {
                    if (leQ <= le && ri <= riQ) {
                        return t[i];
                    }
                    else {
                        pushSons(i);
                        int mi = (le + ri) / 2;
                        return mergeClass()(Query(leQ, riQ, leSon(i), le, mi), Query(leQ, riQ, riSon(i), mi, ri));
                    }
                }
                else {
                    return U :: NIL;
                }
            }
    };

    class U {
        public:
            static U NIL;
            int le;
            int ri;
            int S;

            U() = default;
            U(int __le, int __ri, int __S) {
                le = __le;
                ri = __ri;
                S = __S;
            }

            inline bool operator ==(const U &other) const {
                return (le == other.le &&
                        ri == other.ri &&
                        S == other.S);
            }
    };

    class V {
        public:
            static V NIL;
            int v;

            V() = default;
            V(int __v) {
                v = __v;
            }
    };

    class W {
        public:
            static W NIL;
            int v;

            W() = default;
            W(int __v) {
                v = __v;
            }
    };

    class addClass {
        public:
            inline U operator () (U fi, V se) {
                U Sol;
                Sol.le = fi.le;
                Sol.ri = fi.ri;
                Sol.S = fi.S + se.v;
                return Sol;
            }
            inline V operator () (V fi, V se) {
                V Sol;
                Sol.v = fi.v + se.v;
                return Sol;
            }
    };

    class setClass {
        public:
            inline U operator () (U fi, W se) {
                U Sol;
                Sol.le = fi.le;
                Sol.ri = fi.ri;
                Sol.S = se.v;
                return Sol;
            }
    };

    class mergeClass {
        public:
            inline U operator () (U fi, U se) {
                if (fi == U :: NIL) {
                    return se;
                }
                else {
                    if (se == U :: NIL) {
                        return fi;
                    }
                    else {
                        U Sol;
                        Sol.le = fi.le;
                        Sol.ri = se.ri;
                        Sol.S = max(fi.S, se.S);
                        return Sol;
                    }
                }
            }
    };

    U U :: NIL = U(0, 0, numeric_limits <int> :: min());
    V V :: NIL = V(0);
    W W :: NIL = W(0);
};

using namespace segTreee;

int n;
int m;
vector <W> initVal;

int main() {
    ifstream cin("arbint.in");
    ofstream cout("arbint.out");

    cin >> n;
    cin >> m;
    initVal = vector <W>(n);
    for (int i = 0; i < n; i++) {
        cin >> initVal[i].v;
    }
    segTree <U, V, W, mergeClass, addClass, setClass> T(n, initVal);
    while (m--) {
        int t;
        cin >> t;
        if (t == 0) {
            int le;
            int ri;
            cin >> le >> ri;
            cout << T.Query(le - 1, ri, 1, 0, n).S << "\n";
        }
        else {
            int p;
            int v;
            cin >> p >> v;
            T.setSegment(p - 1, p, W(v), 1, 0, n);
        }
    }
}