#include<fstream>
#include<iostream>
using namespace std;

int N,M,aib[100100];

int suma(int nod) {
    int s=0;
    while(nod) {
        s+=aib[nod];
        nod-=(nod&-nod);
        }
     return s;
}

void update(int nod,int val) {
        while(nod<=N)  {
         aib[nod]+=val;
         nod+=(nod&-nod);
        }
    }

int cautbin(int x) {

    int st,dr,m,s;
    st=0;
    dr=N;
    while(st<=dr) {
        m=(st+dr)/2;
        s=suma(m);
        if(s<=x)
            st=m+1;
        else
            dr=m-1;
        }

    if(suma(m)!=x)
        m--;
    return m;
}

int main () {

     ifstream in("aib.in");
     ofstream out("aib.out");
     int i,a,b,x,k,operatie;
     in>>N>>M;
     for(i=1;i<=N;i++){
        in>>x;
        update(i,x);
     }
     for(i=1;i<=M;i++) {
        in>>operatie;
        if(operatie==0) {
            in>>a>>b;
            update(a,b);
        }

        if(operatie==1) {
             in>>a>>b;
             out<<suma(b)-suma(a-1)<<'\n';
            }
        if(operatie==2) {
                in>>k;
                x=cautbin(k);
                if(suma(x)!=k)
                    out<<"-1"<<'\n';
                else
                    out<<x<<'\n';
                }
    }
    in.close();
    out.close();
    return 0;

}