#include <cstdio>

using namespace std;

int n, aib[100005];

inline int zero(int x) {
    return ((x^(x-1))&x);
}

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

int query(int x) {
    int rasp = 0;
    for(int i = x; i > 0; i-= zero(i)) {
        rasp += aib[i];
    }
    return rasp;
}

int cautbin(int st, int dr, int val) {
    int med, last = -1, z;

    while(st <= dr) {
        med = st + (dr - st) / 2;
        z = query(med);
        if(z == val) {
            last = med;
            dr = med - 1;
        }
        else
        if(z > val) {
            dr = med - 1;
        }else {
            st = med + 1;
        }
    }

    return last;
}

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

    int m, x, t, y;
    scanf("%d%d", &n, &m);

    for(int i = 1; i <= n; ++ i) {
        scanf("%d", &x);
        add(i, x);
    }

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

    return 0;
}