/* 
 * File:   main.cpp
 * Author: salexandru
 *
 * Created on January 17, 2011, 3:04 PM
 */
#include <fstream>
#include <cstdlib>
#define N_MAX 100011

using namespace std;

/*
 * 
 */
int N;
int Aib[N_MAX];
inline void Update( int x, int b )
{
    for( ; x <= N; x+=( x & -x ) )
        Aib[x]+=b;
}
inline int Query( int x )
{
    int s;
    for( s=0; x; x-=( x & -x ) )
        s+=Aib[x];
    return s;
}
inline int Query2( int s, int idx )
{
    int tidx, i=0;
    for( tidx=0; idx; idx>>=1 )
    {
        tidx=i+idx;
        if( tidx <= N )
        {
            if( Aib[tidx] == s )
                return tidx;
            if( Aib[tidx] < s )
            {
                s-=Aib[tidx];
                i=tidx;
            }
        }
    }
    return -1;
}
int main(int argc, char** argv)
{
    int M, i, x, y, idx;
    ifstream in( "aib.in" );
    in>>N>>M;
    for( i=1; i <= N; ++i )
    {
        in>>x;
        Update( i, x );
    }
    idx=1<<(31-__builtin_clz(N));
    ofstream out( "aib.out" );
    for( ; M; --M )
    {
        in>>i;
        switch( i )
        {
            case 0 : in>>x>>y; Update( x, y ); break;
            case 1 : in>>x>>y; out<<(Query(y)-Query(x-1))<<'\n'; break;
            case 2 : in>>x; out<<Query2(x, idx)<<'\n'; break;
        }
    }


    return 0;
}