#include <iostream>
#include <fstream>
#include <iomanip>
using namespace std;
ifstream f ( "aib.in" );
ofstream g ( "aib.out" );
const int NMAX = 100000;
int N, AiB[NMAX + 1];
void add ( int poz, int val )
{
    while ( poz <= N )
    {
        AiB[poz] += val;
        poz += poz & ( -poz );
    }
}
int sum ( int poz )
{
    int  s = 0;

    while ( poz > 0 )
    {
        s += AiB[poz];
        poz &= ( poz - 1 );
    }

    return s;
}
int bsearch2 ( int val )
{
    int p = 1, u = N, poz = -1;

    while ( p <= u )
    {
        int m = ( p + u ) >> 1, s = sum ( m );

        if ( s < val )
            p = m + 1;
        else
        {
            if ( s == val )
                poz = m;

            u = m - 1;
        }
    }

    return poz;
}
int bsearch ( int val )
{
    int i, step;

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

    for ( i = 0; step > 0; step >>= 1 )
        if ( i + step <= N && val >= AiB[i + step] )
        {
            i += step;
            val -= AiB[i];
        }

    return val ? -1 : i;
}
int main()
{
    int M, op, x, y;
    f >> N >> M;

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

    while ( M-- )
    {
        f >> op;

        switch ( op )
        {
        case 0:
            f >> x >> y;
            add ( x, y );
            break;

        case 1:
            f >> x >> y;
            g << sum ( y ) - sum ( x - 1 ) << '\n';
            break;

        case 2:
            f >> x;
            g << bsearch ( x ) << '\n';
        }
    }

    return 0;
}