# include <algorithm>
using namespace std;

# define DIM 1 << 17

int n, m, aib[ DIM ];

int lsb ( int val ) {

    return val & ( val - 1 ) ^ val;
}

int query ( int poz ) {

    int sum;

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

    return sum;
}

int cbin ( int sum ) {

    int st, dr, mij;

    for ( st = 1, dr = n; st <= dr; ) {

        mij = ( st + dr ) / 2;
        if ( query ( mij ) == sum )
            return mij;

        if ( query ( mij ) < sum )
            st = mij + 1;
        else
            dr = mij - 1;
    }

    return -1;
}

void update ( int poz, int val ) {

    for ( ; poz <= n; poz += lsb ( poz ) )
        aib[ poz ] += val;
}

void read () {

    int i, val;

    scanf ( "%d%d", &n, &m );
    for ( i = 1; i <= n; ++ i ) {

        scanf ( "%d", &val );
        update ( i, val );
    }
}

void solve () {

    int i, x, y, tip;

    for ( i = 0; i < m; ++ i ) {

        scanf ( "%d", &tip );
        if ( tip == 0 ) {

            scanf ( "%d%d", &x, &y );
            update ( x, y );
        }
        else if ( tip == 1 ) {

            scanf ( "%d%d", &x, &y );
            printf ( "%d\n", query ( y ) - query ( x - 1 ) );
        }
        else if ( tip == 2 ) {

            scanf ( "%d", &x );
            printf ( "%d\n", cbin ( x ) );
        }
    }
}
int main () {

    freopen ( "aib.in", "r", stdin );
    freopen ( "aib.out", "w", stdout );

    read ();
    solve ();

    return 0;
}