#include <stdio.h>
#define MAX 100005
#define zeros(x) (x & (-x))

int n, m, t, x, y;
int aib[MAX];

void add(int x, int val){
    for(int i = x; i <= n; i += zeros(i))
        aib[i] += val;
}

int sum(int x){
    int s = 0;
    while(x){
        s += aib[x];
        x -= zeros(x);
    }

    return s;
}

int cb(int x){
    int l = 1, r = n, m;

    while(l <= r){
        m = (l + r) / 2;
        int s = sum(m);
        if(s == x)
            return m;
        if(s < x)
            l = m + 1;
        else
            r = m - 1;
    }
    return -1;
}

int main(){
    freopen("aib.in", "r", stdin);
    freopen("aib.out", "r", stdout);
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i){
        scanf("%d", &x);
        add(i, x);
    }

    for(int i = 0; i < m; ++i){
        scanf("%d%d", &t, &x);
        if(t == 0){
            scanf("%d", &y);
            add(x, y);
        }
        else if(t == 1){
            scanf("%d", &y);
            printf("%d\n", sum(y) - sum(x - 1));
        }
        else
            printf("%d\n", cb(x));
    }

    return 0;
}