#include <algorithm>
#include <fstream>

using namespace std;

const char Input[] = "aib.in";
const char Output[] = "aib.out";

const int Dim = 100001;

int N, M;
int aib[Dim];

inline int LSB( int x ) {

    return x & (-x);
}

inline int Que( int poz ) {

    int sum;

    for( sum = 0; poz > 0; poz -= LSB( poz ) )
        sum += aib[poz];

    return sum;
}

inline int CBin( int sum ) {

    int st, dr, mj, sumq;

    st = 1;
    dr = N;

    while( st <= dr ) {

        mj = (st + dr) / 2;
        sumq = Que( mj );

        if( sumq == sum )
            return mj;

        if( Que( mj ) < sum )
            st = mj + 1;
        else
            dr = mj - 1;
    }

    return -1;
}

inline void Upd( int poz, int val ) {

    for( ; poz <= N; poz += LSB( poz ) )
        aib[poz] += val;
}

int main() {

    ifstream fin( Input );
    ofstream fout( Output );

    int i, x, y, tip;

    fin >> N >> M;
    for( i = 1; i <= N; ++i ) {

        fin >> x;
        Upd( i, x );
    }
    while( M-- ) {

        fin >> tip;
        if( tip == 0 ) {

            fin >> x >> y;
            Upd( x, y );
        }
        else if( tip == 1 ) {

            fin >> x >> y;
            fout << Que( y ) - Que( x - 1 ) << "\n";
        }
        else {

            fin >> x;
            fout << CBin( x ) << "\n";
        }
    }

    fin.close();
    fout.close();

    return 0;
}