#include <bits/stdc++.h>

using namespace std;
ifstream in("aib.in");
ofstream out("aib.out");

const int NMAX = 100005;
int aib[NMAX];

void update(int add, int pos, int n) {
    for(; pos <= n; pos += (pos & -pos))
        aib[pos] += add;
}

int query(int pos) {
    int sum = 0;
    for(; pos; pos -= (pos & -pos))
        sum += aib[pos];
    return sum;
}
int main() {
    int n, m;
    in >> n >> m;
    for(int i = 1; i <= n; i ++) {
        int x;
        in >> x;
        update(x, i, n);
    }
    for(int i = 1; i <= m; i ++) {
        int op;
        in >> op;
        if(op == 0) {
            int a, b;
            in >> a >> b;
            update(b, a, n);
        }
        if(op == 1) {
            int a, b;
            in >> a >> b;
            out << (query(b) - query(a - 1)) << "\n";
        }
        if(op == 2) {
            int a;
            in >> a;
            int step, sol = 0;
            bool flag = 0;
            for(step = 1; step <= n; step <<= 1);
            for(; step; step >>= 1) {
                if(sol + step <= n && aib[sol + step] <= a) {
                    sol += step;
                    a -= aib[sol];
                    if(a == 0) {
                        out << sol << "\n";
                        flag = 1;
                        break;
                    }
                }
            }
            if(flag == 0)
                out << -1 << "\n";
        }
    }
    return 0;
}