#include <fstream>

using namespace std;

ifstream f("aib.in");
ofstream g("aib.out");

#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() {
    f >> n >> m;
    int x;
    for (int i = 1; i <= n; ++i) {
        f >> 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) {
        f >> op >> x;
        if (op == 0) {
            f >> y;
            introducere(x, y);
        } else if (op == 1) {
            f >> y;
            g << suma(y) - suma(x - 1) << '\n';
        } else
            g << cautare_binara(x) << '\n';
    }
}

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