#import<bits/stdc++.h>
int N,o,t,x,y,B[100001];

void U(int p,int v){for(int i=p;i<=N;i+=i&-i)B[i]+=v;}

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

int S(int s){

    int i, step;

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

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

            s -= B[i];

            if(!s) return i;
         }
    }

    return -1;
}

int main(){

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

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

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

        t&1 ? f>>y,g<<Q(y)-Q(x-1)<<'\n' : t ? g<<S(x)<<'\n' : (U(x, y),f>>y);
    }

    return 0;
}