#include <cstdio>
using namespace std;

#define LSB(x)  ( (x) & -(x) )
#define Nmax 100002

FILE *f = fopen ( "aib.in", "r" );
FILE *g = fopen ( "aib.out", "w" );

int N, M, AIB[Nmax];

void Add ( int poz, int val ){

    for ( int i = poz; i <= N; i += LSB(i) )
        AIB[i] += val;
}

int Sum ( int x ){
    int ret = 0;
    for ( int i = x; i > 0; i -= LSB(i) )
        ret += AIB[i];
    return ret;
}

int SumaInt ( int a, int b ){
    return Sum ( b ) - Sum ( a - 1 );
}

int bSearch ( int val ){
    int st = 1, dr = N;

    while ( st <= dr ){
        int mid = ( st + dr ) >> 1;
        int s = Sum (mid);

        if ( s == val )
            return mid;

        if ( s < val )
            st = mid + 1;
        else
            dr = mid - 1;
    }
    return -1;
}

int main(){

    int x, y, type;

    fscanf ( f, "%d%d", &N, &M );

    for ( int i = 1; i <= N; ++i ){
        fscanf ( f, "%d", &x );
        Add ( i, x );
    }

    for ( int i = 1; i <= M; ++i ){
        fscanf ( f, "%d", &type );

        if ( type == 0 ){
            fscanf ( f, "%d%d", &x, &y );
            Add ( x, y );
            continue;
        }

        if ( type == 1 ){
            fscanf ( f, "%d%d", &x, &y );
            fprintf ( g, "%d\n", SumaInt ( x, y ) );
            continue;
        }

        if ( type == 2 ){
            fscanf ( f, "%d", &x );
            fprintf ( g, "%d\n", bSearch ( x ) );
        }
    }

    return 0;
}