#include <cstdio>
#include <vector>
using namespace std;

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

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

int N, M, Size;
vector < int > AIB;

void Add ( int poz, int val ){

    for ( int i = poz; i <= Size; 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 x ){
    int st = 1, dr = Size;

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

        if ( AIB[mid] == x )
            return mid;

        if ( AIB[mid] < x )
            st = mid + 1;
        else
            dr = mid - 1;
    }
    return -1;
}

int main(){

    int x, y, type;

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

    for ( Size = 1; Size < N; Size <<= 1 );
    AIB.resize(Size+1);

    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;
}