#include<fstream>
using namespace std;

const int N = 100010;

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

int n,m,aib[N];

inline void change(int poz, int val) {
    int nr,tm;

    while(poz<=n) {

        aib[poz]+=val;

        nr=1; tm=poz;
        while(!(tm&1)) {
            nr<<=1;

            tm>>=1;
        }

        poz+=nr;

    }

}

inline int sum(int poz) {
    int rez=0,nr,tm;

    while(poz>0) {

        rez+=aib[poz];

        nr=1; tm=poz;
        while(!(tm&1)) {
            nr<<=1;

            tm>>=1;
        }

        poz-=nr;

    }

    return rez;
}

int main() {
    int i,op,poz,val,a1,a2,j,a,pas;

    in >> n >> m;

    for(i=1;i<=n;++i) {
        in >> val;

        change(i,val);
    }

    for(i=1;i<=m;++i) {

        in >> op;

        if(op==0) {
            in >> poz >> val;

            change(poz,val);
        }
        if(op==1) {
            in >> a1 >> a2;

            out << sum(a2) - sum(a1-1) << "\n";
        }
        if(op==2) {
            in >> a;

            if(a==0) {
                out << "-1\n";
                continue;
            }

            pas=1<<16;

            for(j=0;pas!=0;pas>>=1)
                if(j+pas<=n && sum(j+pas)<=a)
                    j+=pas;

            if(sum(j)==a)
                out << j << "\n";
            else
                out << "-1\n";
        }
    }

    return 0;
}