#include <vector>
#include <fstream>

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

class FenTree {
  private:
    int n;
    vector<int> bit;

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

  public:
    FenTree(int n) {
        this->n = n;
        bit.resize(n + 1);
    }

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

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

    int query(int left, int right) {
        return query(right) - query(left - 1);
    }

    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 query(hi) == val ? hi : -1;
    }
};

int main() {
    int n, q;
    fin >> n >> q;

    FenTree bit(n);
    for (int i = 1; i <= n; i++) {
        int x; fin >> x;
        bit.update(i, x);
    }

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

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

    fout.close();
    return 0;
}