#include <fstream>

using namespace std;
int A[100010];
int n, t, p, x, a, b, m, k;
void update(int p, int x) {
    for (;p<=n;p+=(p&-p))
        A[p] += x;
}

int query(int p) {
    int sol = 0;
    for (;p;p-=(p&-p))
        sol += A[p];
    return sol;
}

int cp(int k) {
    int aux = k, p, st;
    for (p=1;2*p<=n;p*=2);

    for (st = 0;p;p/=2) {
        if (st + p <= n)
        if (A[st+p] <= k) {
            st += p;
            k -= A[st+p];
        }
    }
    if (query(st) == aux)
        return st;
    else
        return -1;
}

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

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

    for (;m--;) {
        fin>>t;
        if (t == 0) {
            fin>>p>>x;
            update(p, x);
        }
        if (t == 1) {
            fin>>a>>b;
            fout<<query(b) - query(a-1)<<"\n";
        }
        if (t == 2) {
            fin>>k;
            fout<<cp(k)<<"\n";
        }
    }

    return 0;
}