#include <cstdio>

using namespace std;

#define NMAX 100005

int n, m, aib[NMAX];

void introducere(int poz, int nr) {
    while (poz <= n) {
        aib[poz] += nr;
        poz += poz & (-poz);
    }
}

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

int suma(int poz) {
    int s = 0;
    while (poz > 0) {
        s += aib[poz];
        poz -= poz & (-poz);
    }
    return s;
}

int cautare_binara(int nr) {
    int st = 1, dr = n, mij, rez;
    while (st <= dr) {
        mij = (st + dr) / 2;
        rez = suma(mij);
        if (rez == nr)
            return mij;
        if (rez < nr)
            st = mij + 1;
        else
            dr = mij - 1;
    }
    return -1;
}

void prelucrare() {
    int op, x, y;
    for (int i = 1; i <= m; ++i) {
        scanf("%d%d", &op, &x);
        if (op == 0) {
            scanf("%d", &y);
            introducere(x, y);
        } else if (op == 1) {
            scanf("%d", &y);
            printf("%d\n", suma(y) - suma(x - 1));
        } else
            printf("%d\n", cautare_binara(x));
    }
}

int main() {
    citire();
    prelucrare();
    return 0;
}