#include <fstream>
//#include <iostream>
using namespace std;
ifstream cin("aib.in");
ofstream cout("aib.out");
struct aint {
    int a, b;
    int l, r;
    int v;
};
aint pre[200001];
int mems = 0;
void build(int node) {
    int l = pre[node].l;
    int r = pre[node].r;
    if(l != r) {
        pre[node].a = (mems++);
        pre[pre[node].a].l = l;
        pre[pre[node].a].r = l + (r - l + 1)/2 - 1;
        pre[pre[node].a].a = -1;
        pre[pre[node].a].b = -1;
        pre[pre[node].a].v = 0;
        pre[node].b = (mems++);
        pre[pre[node].b].l = l + (r - l + 1)/2;
        pre[pre[node].b].r = r;
        pre[pre[node].b].a = -1;
        pre[pre[node].b].b = -1;
        pre[pre[node].b].v = 0;
        build(pre[node].a);
        build(pre[node].b);
    }
}
int query(int node, int l, int r) {
    if((l == pre[node].l) && (r == pre[node].r))
        return pre[node].v;
    else if(r <= pre[pre[node].a].r)
        return query(pre[node].a, l, r);
    else if(l >= pre[pre[node].b].l)
        return query(pre[node].b, l, r);
    else
        return query(pre[node].a, l, pre[pre[node].a].r) + query(pre[node].b, pre[pre[node].b].l, r);
}
void add(int node, int add, int target) {
    while(true) {
        pre[node].v += add;
        if(pre[node].a == -1)
            return;
        if(pre[pre[node].a].r >= target)
            node = pre[node].a;
        else
            node = pre[node].b;
    }
}
int firstk(int v, int node) {
    int up = -1;
    int sum = pre[node].v;
    if(sum < v) {
        return -1;
    }
    while(true) {
        if(sum < v) {
            node = pre[pre[up].b].a;
            if(node == -1) {
                return -1;
            }
            up = pre[up].b;
            sum += pre[node].v;
        } else if(sum > v) {
            sum -= pre[node].v;
            up = node;
            node = pre[node].a;
            if(node == -1) {
                break;
            }
            sum += pre[node].v;
        } else {
            return pre[node].r;
        }
    }
    return -1;
}
int root;
int main() {
    int n, m;
    cin>>n>>m;
    root = (mems++);
    pre[root].l = 1;
    pre[root].r = n;
    pre[root].v = 0;
    pre[root].a = -1;
    pre[root].b = -1;
    build(root);
    for(int x = 1, tmp; x<=n; x++) {
        cin>>tmp;
        add(root, tmp, x);
    }
    for(int x = 0, req; x<m; x++) {
        cin>>req;
        if(req == 0) {
            int target, add_;
            cin>>target>>add_;
            add(root, add_, target);
        } else if(req == 1) {
            int l, r;
            cin>>l>>r;
            cout<<query(root, l, r)<<'\n';
        } else {
            int v;
            cin>>v;
            cout<<firstk(v, root)<<'\n';
        }
    }
    return 0;
}