#include <cstdlib>
#include <fstream>
#define Nmax 100111

/*
 *
 */
using namespace std;
int N;
int Aib[Nmax];
inline void UpDate( int x, int y )
{
    for( ; x <= N; x+=( x & -x ) )
        Aib[x]+=y;
}
inline int Query1( int x )
{
    int s;
    for( s=0; x; x-=( x & -x ) )
        s+=Aib[x];
    return s;
}
inline int Query2( int x, int idx )
{
    int i, tidx;
    for( i=0; idx; idx>>=1 )
    {
        tidx=idx+i;
        if( tidx <= N )
        {
            if( x == Aib[tidx] )
                return tidx;
            if( x > Aib[tidx] )
            {
                x-=Aib[tidx];
                i=tidx;
            }
        }
    }
    return -1;
}
int main( void )
{
    int M, i, a, b, idx;
    ifstream in( "aib.in" );
    in>>N>>M;
    for( i=1; i <= N; ++i )
    {
        in>>a;
        UpDate( i, a );
    }
    for( idx=1; idx < N; idx<<=1 );
    ofstream out( "aib.out" );
    for( ; M; --M )
    {
        in>>i;
        switch( i )
        {
            case 0 : in>>a>>b, UpDate( a, b ); break;
            case 1 : in>>a>>b, out<<( Query1(b)-Query1(a-1) )<<'\n'; break;
            default : in>>a, out<<Query2( a, idx )<<'\n';
        }
    }
    return EXIT_SUCCESS;
}