/* 
 * File:   main.cpp
 * Author: VirtualDemon
 *
 * Created on April 8, 2010, 8:58 AM
 */
#include <cstdlib>
#include <fstream>
#define Nmax 100001

/*
 * 
 */
using namespace std;
int N, stop;
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=0;
    for( ; x; x-=( x & -x ) )
        S+=AIB[x];
    return S;
}
inline int Query2( int x )
{
    int i, tidx, idx;
    for( i=0, idx=stop; idx; idx>>=1 )
    {
        tidx=i+idx;
        if( tidx <= N )
        {
            if( x == AIB[tidx] )
                return tidx;
            if( x > AIB[tidx] )
            {
                i=tidx;
                x-=AIB[tidx];
            }
        }
    }
    return -1;
}
int main( void )
{
    int M, a, b;
    ifstream in( "aib.in" );
    in>>N>>M;
    for( b=1; b <= N; ++b )
    {
        in>>a;
        UpDate( b, a );
    }
    for( stop=1; stop < N; stop<<=1 );
    ofstream out( "aib.out" );
    for( ; M; --M )
    {
        in>>a>>b;
        if( !a )
        {
            in>>a;
            UpDate( b, a );
        }
        else if( 1 == a )
             {
                in>>a;
                out<<( Query1(a)-Query1(b-1) )<<'\n';
             }
             else out<<Query2(b)<<'\n';
    }
    return EXIT_SUCCESS;
}