# include <cstring>
# include <cstdio>

const char *FIN = "aib.in", *FOU = "aib.out";

int aib[100005];
int N, M;

int cb (int val) {
    int i, cnt;
    for (cnt = 1; cnt << 1 <= N; cnt <<= 1);
    for (i = 0; cnt; cnt >>= 1)
        if (i + cnt <= N && aib[i + cnt] <= val) {
            i += cnt, val -= aib[i];
            if (val == 0) return i;
        }
    return -1;
}

void update (int nod, int val) {
    for (; nod <= N; aib[nod] += val, nod += nod ^ (nod & (nod - 1)));
}

int query (int nod) {
    int sol;
    for (sol = 0; nod > 0; sol += aib[nod], nod -= nod ^ (nod & (nod - 1)));
    return sol;
}

int main (void) {
    freopen (FIN, "r", stdin);
    freopen (FOU, "w", stdout);

    scanf ("%d %d", &N, &M);
    for (int i = 1, x; i <= N; ++i) {
        scanf ("%d", &x);
        update (i, x);
    }
    for (int i = 1, x, y, tip; 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 {
            scanf ("%d", &x);
            printf ("%d\n", cb (x));
        }
    }
}