#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 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;

    int v = y, i, s, z = -1;

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

    for(i = 0; s; s >>= 1)

         if(i + s <= N && v >= B[i + s])
         {
            (v -= B[i += s]) || (z = i, s = 0);
         }

        switch(t)
        {
            case 0: f>>x;U(y);
break;
            case 1: f>>x;g<<Q(x)-Q(y-1)<<'\n';
break;
            case 2: g<<z<<'\n';
        }
    }
}