#include <fstream>

using namespace std;
ifstream in("aib.in");
ofstream out("aib.out");
int aib[100005];
int n;
void update(int poz,int x) {
    for(; poz<=n; poz+=poz&(-poz))
        aib[poz]+=x;
}
int query(int poz) {
    int s=0;
    for(; poz>0; poz-=poz&(-poz))
        s+=aib[poz];
    return s;
}
int main() {
    int m,i,x,c,a,b;
    in>>n>>m;
    for(i=1; i<=n; i++) {
        in>>x;
        update(i,x);
    }
    for(i=1; i<=m; i++) {
        in>>c;
        if(c==0) {
            in>>a>>b;
            update(a,b);
        } else if(c==1) {
            in>>a>>b;
            out<<query(b)-query(a-1)<<'\n';
        } else if(c==2) {
            in>>a;
            int med,st,dr,ok=0;
            st=1;
            dr=n;
            while(st<=dr) {
                med=(st+dr)/2;
                if(query(med)<a)
                    st=med+1;
                else if(query(med)>a)
                    dr=med-1;
                else if(query(med)==a) {
                    ok=1;
                    break;
                }
            }
            if(ok==1)
                out<<med<<'\n';
            else out<<-1<<'\n';
        }
    }
    return 0;
}