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

lli N, M, aib[DIM];

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

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

}

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

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

    return R;
}

void Citire(){
lli i, x;

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

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

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

    }

}

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

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

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

        if( tip == 0 ){

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

        }

        if( tip == 1 ){

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

        }

        if( tip == 2 ){

            fscanf(f,"%lld",&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,"%lld\n",p);
            else
                fprintf(g,"-1\n");

        }

    }

}

int main(){

    Citire();
    Rezolvare();

return 0;
}