#include <fstream>

using namespace std;

ifstream fin("aib.in");
ofstream fout("aib.out");

const int nmax= 100000;

int n;
int ft[nmax+1];

void ft_update( int p, int x ) {
    for ( int i= p; i<=n; i= 2*i-(i&(i-1)) ) {
        ft[i]+= x;
    }
}

int ft_query( int p ) {
    int sol= 0;
    for ( int i= p; i>0; i&= i-1 ) {
        sol+= ft[i];
    }
    return sol;
}

int main(  ) {
    int m;
    fin>>n>>m;

    int n2;
    for ( n2=1; n2<n; n2<<=1 ) {
    }

    for ( int i= 1; i<=n; ++i ) {
        int x;
        fin>>x;
        ft_update(i, x);
    }

    for ( int i= 1; i<=m; ++i ) {
        int x, y, z;
        fin>>x;
        if ( x==2 ) {
            fin>>y;
            
            int step= n2, k;
            for ( k= n; step; step>>=1 ) {
                if ( k>step && ft_query(k-step)>=y ) {
                    k-= step;
                }
            }
            
            if ( ft_query(k)!=y ) {
                fout<<"-1\n";
            } else {
                fout<<k<<"\n";
            }

        } else if ( x==1 ) {
            fin>>y>>z;
            fout<<ft_query(z)-ft_query(y-1)<<"\n";
        } else {
            fin>>y>>z;
            ft_update(y, z);
        }
    }

    return 0;
}