#include<cstdio>
#include<fstream>
#include<cstring>

#define MAXN 100002

using namespace std;
typedef int32_t var;

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


inline var nr_zero(const var &x) {
    return ( (x ^ (x - 1)) + 1 )/ 2;
}


var n;
var *A;

void add(const var &val, var ind) {
    for(; ind <= n; ind += nr_zero(ind)) {
        A[ind] += val;
    }
}

var s;
var query(var ind) {
    s = 0;
    for(; ind > 0 ; ind -= nr_zero(ind)) {
        s += A[ind];
    }
    return s;
}

var step, i;
int poz(var sum) {
    i = 0;
    for(step=1; step<=n; step<<=1);
    for(step>>=1; step; step>>=1) {
        if(i+step<=n && query(i+step) < sum) {
            i += step;
        }
    }
    return (query(i+1) == sum) ? i+1 : -1;
}

int main() {
    var t, m, type, a, b;

    fin>>n>>m;
    A = new var[n+2];
    fill(A, A+n+1, 0);

    for(var i=1; i<=n; i++) {
        fin>>t;
        add(t, i);
    }
    while(m--) {
        fin>>type;
        if(type == 0) {
            fin>>a>>b;
            add(b, a);
        } else if(type == 1) {
            fin>>a>>b;
            fout<<query(b) - query(a-1)<<'\n';
        } else {
            fin>>a;
            fout<<poz(a)<<'\n';
        }
    }
    return 0;
}