#include <fstream>
#define NMAX 100010

std::ifstream fin("aib.in");
std::ofstream fout("aib.out");

int n, q;
int aib[NMAX];

inline int lsb(int x) {
    return x & (-x);
}

void update(int pos, int val) {
    for (int i = pos; i <= n; i += lsb(i))
        aib[i] += val;
}

int query(int pos) {
    int sum = 0;
    for (int i = pos; i >= 1; i -= lsb(i))
        sum += aib[i];
    return sum;
}

int search(int val) {
    int md, lo = 0, hi = n + 1;
    while (hi - lo > 1) {
        md = (lo + hi) >> 1;
        if (query(md) < val)
            lo = md;
        else
            hi = md;
    }
    return hi <= n ? hi : -1;
}

int main() {
    fin >> n >> q;
    for (int i = 1; i <= n; i++) {
        int x; fin >> x;
        update(i, x);
    }

    for (int it = 0; it < q; it++) {
        int t, x, y;
        fin >> t >> x;
        if (t < 2)
            fin >> y;

        if (!t)
            update(x, y);
        else if (t == 1)
            fout << query(y) - query(x - 1) << '\n';
        else
            fout << search(x) << '\n';
    }

    fout.close();
    return 0;
}