#include <bits/stdc++.h>

using namespace std;

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

int n, m, bmx;
vector<int> a;

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

struct Aib {
    vector<int> v;

    void upd(int x, int poz) {
        while (poz <= n) {
            v[poz] += x;
            poz += lsb(poz);
        }
    }

    int sum(int poz) {
        int s = 0;
        while (poz) {
            s += v[poz];
            poz -= lsb(poz);
        }
        return s;
    }
} aib;

int caut(int k) {
    int b = bmx;
    int poz = 0;
    while (b >= 0) {
        int s = aib.sum(poz + (1 << b));
        if (s < k) {
            poz += (1 << b);
        }
        b--;
    }
    poz++;
    return (poz <= n ? poz : -1);
}

int main() {
    fin >> n >> m;
    a = vector<int>(n + 1);
    aib.v = vector<int>(n + 1);
    while ((1 << (bmx + 1)) <= n) {
        bmx++;
    }

    for (int i = 1; i <= n; i++) {
        fin >> a[i];
        aib.upd(a[i], i);
    }

    int t, x, y;
    for (int i = 0; i < m; i++) {
        fin >> t;
        if (t == 0) {
            fin >> x >> y;
            aib.upd(y, x);
        } else if (t == 1) {
            fin >> x >> y;
            int s = aib.sum(y) - aib.sum(x - 1);
            fout << s << "\n";
        } else {
            fin >> x;
            fout << caut(x) << "\n";
        }
    }
}