#include <fstream>

using namespace std;

ifstream fin ("aib.in");
ofstream fout ("aib.out");

int n, m;
int v[100001], c[100001];

void citire_si_setup();
int putere2k ( int x );
void adauga ( int poz, int val );
int sum ( int x );
int caut ( int st, int dr, int val );

int main()
{
    int i, a, b, cer, j;

    citire_si_setup();
    for ( i = 1 ; i <= m ; i++ )
    {
        fin >> cer >> a;
        if ( cer == 0 )
        {
            fin >> b;
            adauga ( a, b );
        }
        else if ( cer == 1 )
        {
            fin >> b;
            fout << sum ( b ) - sum ( a - 1 ) << '\n';
        }
        else
        {
            j = 1;
            while ( c[j] <= a && j <= n ) j = j << 1;

            if ( j > n ) fout << caut ( j >> 1, n, a ) << '\n';
            else fout << caut ( j >> 1, j, a ) << '\n';
        }
    }

    return 0;
}

void citire_si_setup()
{
    int i;
    int s[100001];

    fin >> n >> m;
    s[0] = 0;
    for ( i = 1 ; i <= n ; i ++ ) fin >> v[i], s[i] = s[i-1] + v[i];

    for ( i = 1 ; i <= n ; i += 2 ) c[i] = v[i];
    for ( i = 2 ; i <= n ; i += 2 ) c[i] = s[i] - s[i-putere2k(i)];
}

int putere2k ( int x )
{
    return x & ( x ^ ( x - 1 ) );
}

void adauga ( int poz, int val )
{
    int i;

    for ( i = poz ; i <= n ; i += putere2k ( i ) ) c[i] += val;
}

int sum ( int x )
{
    int i, s = 0;

    for ( i = x ; i > 0 ; i -= putere2k ( i ) ) s += c[i];

    return s;
}

int caut ( int st, int dr, int val )
{
    int r = -1, mij;

    while ( st <= dr )
    {
        mij = ( st + dr ) / 2;
        if ( sum ( mij ) < val ) st = mij + 1;
        else
        {
            if ( sum ( mij ) == val ) r = mij;
            dr = mij - 1;
        }
    }

    return r;
}