/* 
 * File:   main.cpp
 * Author: virtualdemon
 *
 * Created on April 28, 2010, 6:54 PM
 */
#include <cstdlib>
#include <fstream>
#define Nmax 100011

/*
 * 
 */
using namespace std;
int N, log2N;
int aib[Nmax];
inline void UpDate( int x, int y )
{
    for( ; x <= N; x+=( x & -x ) )
        aib[x]+=y;
}
inline int Sum( int x )
{
    int s=0;
    for( ; x; x-=( x & -x ) )
        s+=aib[x];
    return s;
}
inline int Search( int sum )
{
    int idx, tidx, i;
    for( i=0, idx=log2N; idx; idx>>=1 )
    {
        tidx=i+idx;
        if( tidx <= N )
        {
            if( sum == aib[tidx] )
                return tidx;
            if( sum > aib[tidx] )
            {
                sum-=aib[tidx];
                i=tidx;
            }
        }
    }
    return -1;
}
int main(int argc, char** argv)
{
    int M, x, i=1;
    ifstream in( "aib.in" );
    for( in>>N>>M; i <= N; ++i )
    {
        in>>x;
        UpDate( i, x );
    }
    for( log2N=1; log2N < N; log2N<<=1 );
    ofstream out( "aib.out" );
    for( ; M; --M )
    {
        in>>i;
        if( !i )
        {
            in>>i>>x;
            UpDate( i, x );
        }
        else if( 1 == i )
             {
                in>>i>>x;
                out<<( Sum(x)-Sum(i-1) )<<'\n';
             }
             else {
                    in>>x;
                    out<<Search(x)<<'\n';
                  }
    }
    return (EXIT_SUCCESS);
}