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

ifstream in("arbint.in");
ofstream out("arbint.out");

const int DIM = 1e5 + 5;

template <class NodeType, class UpdateType>
class LazySegmentTree {
private:
    int siz, _lef, _rig;
    NodeType *sgt; UpdateType val, *arr;
    
    NodeType mergeSons(NodeType son1, NodeType son2);
    
    void updateNode(NodeType &nod, UpdateType val);
    void updateLazy(NodeType &nod, NodeType &son1, NodeType &son2, bool ok);
    
    void _updateLazy(int nod, int lef, int rig) {
        if (lef == rig)
            updateLazy(sgt[nod], sgt[nod], sgt[nod], false);
        else
            updateLazy(sgt[nod], sgt[nod << 1], sgt[nod << 1 | 1], false);
    }
    
    void buildTree(int nod, int lef, int rig) {
        if (lef == rig)
            updateNode(sgt[nod], arr[lef]);
        else {
            int mid = (lef + rig) >> 1;
            
            buildTree(nod << 1, lef, mid);
            buildTree(nod << 1 | 1, mid + 1, rig);
            
            sgt[nod] = mergeSons(sgt[nod << 1], sgt[nod << 1 | 1]);
        }
    }
    
    void updateTree(int nod, int lef, int rig) {
        if (_lef <= lef and rig <= _rig)
            updateNode(sgt[nod], val);
        else {
            int mid = (lef + rig) >> 1;
            
            _updateLazy(nod << 1, lef, mid);
            _updateLazy(nod<< 1 | 1, mid + 1, rig);
            
            if (_lef <= mid)
                updateTree(nod << 1, lef, mid);
            if (mid < _rig)
                updateTree(nod << 1 | 1, mid + 1, rig);
            
            sgt[nod] = mergeSons(sgt[nod << 1], sgt[nod << 1 | 1]);
        }
    }
    
    NodeType queryTree(int nod, int lef, int rig) {
        if (_lef <= lef and rig <= _rig)
            return sgt[nod];
        else {
            int mid = (lef + rig) >> 1;
            
            _updateLazy(nod << 1, lef, mid);
            _updateLazy(nod << 1 | 1, mid + 1, rig);
            
            if (_rig <= mid)
                return queryTree(nod << 1, lef, mid);
            if (mid < _lef)
                return queryTree(nod << 1 | 1, mid + 1, rig);
            
            return mergeSons(queryTree(nod << 1, lef, mid),
                             queryTree(nod << 1 | 1, mid + 1, rig));
        }
    }
public:
    LazySegmentTree(int dim, NodeType nil) {
        sgt = new NodeType[dim << 2]; siz = dim;
        for (int i = 0; i < (dim << 2); ++i)
            sgt[i] = nil;
    }
    
    inline void resize(int dim) {
        siz = dim;
    }
    
    inline void build(UpdateType *aux) {
        arr = aux; buildTree(1, 1, siz);
    }
    
    inline void update(int lef, int rig, UpdateType cns) {
        _lef = lef; _rig = rig; val = cns;
        updateTree(1, 1, siz);
    }
    
    inline NodeType query(int lef, int rig) {
        _lef = lef; _rig = rig;
        return queryTree(1, 1, siz);
    }
}; LazySegmentTree<pair<int, int>, int> mySegmentTree(DIM, pair<int, int>(0, 0));

template <class NodeType, class UpdateType>
void LazySegmentTree<NodeType, UpdateType>::updateNode(NodeType &nod, UpdateType val) {
    nod.second = val;
}

template <class NodeType, class UpdateType>
NodeType LazySegmentTree<NodeType, UpdateType>::mergeSons(NodeType son1, NodeType son2) {
    return make_pair(0, max(son1.second, son2.second));
}

template <class NodeType, class UpdateType>
void LazySegmentTree<NodeType, UpdateType>::updateLazy(NodeType &nod, NodeType &son1, NodeType &son2, bool ok) {
    if (ok)
        son1.first += nod.first, son2.first += nod.first;
    nod.second += nod.first; nod.first = 0;
}

int arr[DIM];

int main(void)
{
    int n, q;
    in >> n >> q;
    
    for (int i = 1; i <= n; ++i)
        in >> arr[i];
    
    mySegmentTree.resize(n);
    mySegmentTree.build(arr);
    
    while (q--) {
        int t, x, y;
        in >> t >> x >> y;
        
        switch(t) {
            case 1:
                mySegmentTree.update(x, x, y); break;
            case 0:
                out << mySegmentTree.query(x, y).second << "\n"; break;
        }
    }
    
    return 0;
}