#include <fstream>

using namespace std;

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

#define NMAX 100005

int n, m, aib[NMAX];

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

void citire() {
    f >> n >> m;
    int x;
    for (int i = 1; i <= n; ++i) {
        f >> x;
        actualizare(i, x);
    }
}

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

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

void parcurgere() {
    int tip, a, b;
    for (int i = 1; i <= m; ++i) {
        f >> tip >> a;
        if (!tip) {
            f >> b;
            actualizare(a, b);
        } else if (tip == 1) {
            f >> b;
            g << suma(b) - suma(a - 1) << '\n';
        } else
            g << cautare_binara(a) << '\n';
    }
}

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