#include <bits/stdc++.h>
#define lsb(x) (x & -x)

using namespace std;

const int MAXN = 1e5 , MAXP2 = 65536;
struct {
    int a[MAXN + 1] , sz;
    void update ( int poz , int val ) {
        if ( poz <= sz ) {
            a[poz] += val;
            update ( poz + lsb ( poz ) , val );
        }
    }
    int query1 ( int poz ) {
        if ( poz < 1 )
            return 0;
        return a[poz] + query1 ( poz - lsb ( poz ) );
    }
    int query2 ( int l , int r ) {
        return query1 ( r ) - query1 ( l - 1 );
    }
    int cautbin ( int k ) {
        int poz , i , crs;

        poz = crs = 0;
        for ( i = MAXP2 ; i > 0 ; i >>= 1 )
            if ( poz + i <= sz && crs + a[poz + i] < k ) {
                crs += a[poz + i];
                poz += i;
            }

        poz++;
        if ( query1 ( poz ) != k )
            return -1;
        return poz;
    }
} aib;
int main () {
    ifstream fin ( "aib.in" );
    ofstream fout ( "aib.out" );
    int n , m , i , a , tip , b;

    fin >> n >> m;
    aib.sz = n;
    for ( i = 1 ; i <= n ; i++ ) {
        fin >> a;
        aib.update ( i , a );
    }
    for ( i = 0 ; i < m ; i++ ) {
        fin >> tip >> a;
        if ( tip == 0 ) {
            fin >> b;
            aib.update ( a , b );
        } else if ( tip == 1 ) {
            fin >> b;
            fout << aib.query2 ( a , b ) << '\n';
        } else
            fout << aib.cautbin ( a ) << '\n';
    }

    return 0;
}