#include <stdio.h>
using namespace std;

#define Nmax 100005

int n, m;
int aib[Nmax];

inline int nrZ(int x){ // returneza 2 la puterea celui mai nesemnificativ bit (sau 2 la puterea numarului de zerouri terminale)
    return ( (x&(x-1))^x );
}

inline void update(int ind, int val){
    while(ind <= n){
        aib[ind] += val;
        ind += nrZ(ind);
    }
}

void read(){
    int x;
    scanf("%i %i", &n, &m);
    for(int i = 1; i <= n; ++i){
        scanf("%i", &x);
        update(i, x);
    }
}

inline int query(int x){
    int s = 0;
    while( x > 0 ){
        s += aib[x];
        x -= nrZ(x);
    }

    return s;
}

inline int search(int x){
    int k = 1;
    while(k < n) k <<= 1;

    for(int i = 0; k; k >>= 1){
        if(i + k <= n)
            if(x >= aib[i+k]){
                i += k;
                x -= aib[i];
                if( !x ) return i;
            }
    }

    return -1;
}

void solve(){
    int op, a, b, s;
    for(int i = 1; i <= m; ++i){
        scanf("%i", &op);

        if(op == 0){
            scanf("%i %i", &a, &b);
            update(a, b);
        }
        else if(op == 1){
            scanf("%i %i", &a, &b);
            s = query(b) - query(a-1);
            printf("%i\n", s);
        }
        else if(op == 2){
            scanf("%i", &a);
            printf("%i\n", search(a));
        }
    }
}

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

    read();
    solve();

    fclose(stdin);
    fclose(stdout);

    return 0;
}