#include<cstdio>
#define DIM 100005
#define zeros(x) ( ( x ^ (x-1) ) & x )
FILE *f=fopen("aib.in","r"), *g=fopen("aib.out","w");

int N, M, aib[DIM];

void Add( int nr, int poz ){
int i;

    for(i=poz;i<=N;i+=zeros(i))
        aib[i] += nr;

}

int Sum( int poz ){
int i, R = 0;

    for(i=poz;i>=1;i-=zeros(i))
        R += aib[i];

    return R;
}

void Citire(){
int i, x;

    fscanf(f,"%d %d\n",&N,&M);

    for(i=1;i<=N;i++){

        fscanf(f,"%d",&x);
        Add(x,i);

    }

}

void Rezolvare(){
int i, tip, a, b, p, u, mij, sum;

    for(i=1;i<=M;i++){

        fscanf(f,"%d",&tip);

        if( tip == 0 ){

            fscanf(f,"%d %d",&a,&b);
            Add(b,a);

        }

        if( tip == 1 ){

            fscanf(f,"%d %d",&a,&b);
            fprintf(g,"%d\n", Sum(b) - Sum(a-1) );

        }

        if( tip == 2 ){

            fscanf(f,"%d",&a);

            p = 1;
            u = N;

            while( p <= u ){

                mij = ( p + u ) / 2;

                if( Sum(mij) >= a )
                    u = mij-1;
                else
                    p = mij+1;

            }

            if( Sum(p) == a )
                fprintf(g,"%d\n",p);
            else
                fprintf(g,"-1\n");

        }

    }

}

int main(){

    Citire();
    Rezolvare();

return 0;
}