#include <cstdio>
#define nrzero(x) (x ^ (x - 1)) & x
using namespace std;
const int NMAX = 100005;
int aib[NMAX];
void update(int val, int poz, int n) {
    while(poz <= n) {
        aib[poz] += val;
        poz += nrzero(poz);
    }
}
int query(int poz, int n) {
    int sol = 0;
    while(poz) {
        sol += aib[poz];
        poz -= nrzero(poz);
    }
    return sol;
}
int bs(int a, int n) {
    int st = 1, dr = n, last = -1;
    while(st <= dr) {
        int mij = (st + dr) / 2, suma = query(mij, n);
        if(suma < a) {
            st = mij + 1;
        }
        else {
            if(a == suma) {
                last = mij;
            }
            dr = mij - 1;
        }
    }
    return last;
}

int main() {
    int n, m;
    freopen("aib.in", "r", stdin);
    freopen("aib.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i) {
        int x;
        scanf("%d", &x);
        update(x, i, n);
    }
    for(int nrq = 0; nrq < m; ++nrq) {
        int op, a;
        scanf("%d%d", &op, &a);
        if(op == 0) {
            int b;
            scanf("%d", &b);
            update(b, a, n);
        }
        else if(op == 1) {
            int b;
            scanf("%d", &b);
            printf("%d\n", query(b, n) - query(a - 1, n));
        }
        else if(op == 2) {
            printf("%d\n", bs(a, n));
        }
    }
    return 0;
}