#import<fstream>
int N,o,t,x,y,B['썐'];

int U(int p){for(;p<=N;p+=p&-p)B[p]+=x;}

int Q(int p){int s=0;for(;p;p&=~-p)s+=B[p];return s;}

int S(int v){

    int i, step;

    for(step = 1; step <= N; step <<= 1);

    for(i = 0; step; step >>= 1)
    {
         if(i + step <= N && v >= B[i + step])
         {
            i += step;

            v -= B[i];

            if(!v) return i;
         }
    }

    return -1;
}

int main(){

    std::ifstream f("aib.in");
    std::ofstream g("aib.out");

    for(f>>N>>o;N/++y;U(y))f>>x;

    for(;o--;)
    {
        f>>t>>y;



        if(t < 2) f>>x;

        if(t == 0) U(y);

        else g<<(t&1 ? Q(x)-Q(y-1) : S(y))<<'\n';
    }
}