#include <iostream>
#include <fstream>
#define nl '\n'
using namespace std;
ifstream f ( "aib.in" );
ofstream g ( "aib.out" );
const int NMAX = 100002;
inline int zero ( int x )
{
    return ( x ^ ( x - 1 ) ) &x;
}
int N;
int aib[NMAX];
void Update ( int val, int poz )
{
    for ( int i = poz; i <= N; i += zero ( i ) )
        aib[i] += val;
}
int Sum ( int x )
{
    int sumTot = 0;

    for ( int i = x; i >= 1; i -= zero ( i ) )
        sumTot += aib[i];

    return sumTot;
}
int Search ( int toFind )
{
    int pow2 = 1, poz = 0;

    for ( pow2 = 1; pow2 <= N; pow2 <<= 1 );

    for ( poz; pow2; pow2 >>= 1 )
    {
        if ( poz + pow2 <= N )
        {
            if ( toFind >= aib[poz + pow2] )
            {
                poz += pow2;
                toFind -= aib[poz];

                if ( toFind == 0 )
                    return poz;
            }
        }
    }

    return -1;
}
int main()
{
    int Q;
    f >> N >> Q;

    for ( int i = 1; i <= N; i++ )
    {
        int nr;
        f >> nr;
        Update ( nr, i );
    }

    while ( Q-- )
    {
        int op, a, b;
        f >> op >> a;

        if ( op == 0 )
        {
            f >> b;
            Update ( b, a );
        }
        else
            if ( op == 1 )
            {
                f >> b;
                g << Sum ( b ) - Sum ( a - 1 ) << nl;
            }
            else
            {
                g << Search ( a ) << nl;
            }
    }

    return 0;
}