/* 
 * File:   main.cpp
 * Author: bitone
 *
 * Created on October 13, 2010, 8:36 PM
 */
#include <fstream>
#include <cstdlib>
#define MAX_N 100011

using namespace std;

/*
 * 
 */
int N;
int aib[MAX_N];
inline void Update( int x, int& s )
{
    for( ; x <= N; x+=( x & -x ) )
        aib[x]+=s;
}
inline int Query1( int x )
{
    int s=0;
    for( ; x; x-=( x & -x ) )
        s+=aib[x];
    return s;
}
inline int Query2( int idx, int a )
{
    int tidx, i=0;
    for( ; idx; idx>>=1 )
    {
        tidx=i+idx;
        if( tidx <= N )
        {
            if( a == aib[tidx] )
                return tidx;
            else if( a > aib[tidx] )
                    a-=aib[tidx], i=tidx;
        }
    }
    return -1;
}
int main(int argc, char** argv)
{
    int M, a, b, i, 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;
        if( 0 == i )
        {
            in>>a>>b;
            Update( a, b );
        }
        else if( 1 == i )
             {
                in>>a>>b;
                out<<( Query1(b)-Query1(a-1) )<<'\n';
             }
             else {
                    in>>a;
                    out<<Query2( idx, a )<<'\n';
                  }
    }
    return EXIT_SUCCESS;
}