#include <cstdio>
using namespace std;

long n, m;
short v[100001];
long aib[100001];

void update(long x, long val) {
    while(x <= n) {
        aib[x] += val;
        x += (x & (-x));
    }
}

void createAIB() {
    long i;
    for(i = 1; i <= n; i++)
        update(i, v[i]);
}

long basicQuery(long x) {
    long rez = 0;
    while(x) {
        rez += aib[x];
        x -= (x & (-x));
    }
    return rez;
}

long query(long x, long y) {
    return basicQuery(y) - basicQuery(x - 1);
}

long smpos(long a) {
    long x, y;
    long m;
    long w;
    x = 1;
    y = n;
    while(x + 1 < y) {
        m = (x + y + 1) / 2;
        w = basicQuery(m);
        if(w >= a) {
            y = m;
        } else {
            x = m;
        }
    }
    if(basicQuery(x) == a)
        return x;
    else if(basicQuery(y) == a)
        return y;
    else return -1;
}

long c, a, b;

int main() {
    long i, j;
    freopen("aib.in", "r", stdin);
    freopen("aib.out", "w", stdout);
    scanf("%ld %ld", &n, &m);
    for(i = 1; i <= n; i++) {
        scanf("%ld", &v[i]);
    }
    createAIB();
    for(i = 1; i <= m; i++) {
        scanf("%ld %ld", &c, &a);
        if(c == 0 || c == 1)
            scanf("%ld", &b);
        if(c == 1)
            printf("%ld\n", query(a, b));
        else if(c == 0)
            update(a, b);
        else printf("%ld\n", smpos(a));
    }
    return 0;
}