#include <bits/stdc++.h>
using namespace std;

using ll = long long;

class aib{
    int n;
    vector<ll> buf;
public:
    aib(const int N): n(1<<(int)ceil(log2(N + 10))), buf(n){
        for(int i = N+1; i < n; ++i) update(i, 1); }
    bool update(int p, const int d){
        for( ; p < n; p += p&-p) buf[p] += d; }
    ll query(int p){
        ll r = 0;
        for( ; p; p -= p&-p) r += buf[p];
        return r; }
    ll query(int st, int dr){
        return query(dr) - query(st-1); }
    int cbin(ll k){
        int r = 0;
        for(int step = n/2; step; step /= 2)
            if(k >= buf[r+step]) r+=step, k-=buf[r];
        return k ? -1 : r; } };

int main(){
    ifstream f("aib.in");
    ofstream g("aib.out");
    int n, m;
    f >> n >> m;
    aib arb(n);
    for(int i = 1, x; i <= n; ++i)
        f >> x, arb.update(i, x);
    for(int i = 0, t, a, b; i < m; ++i){
        f >> t;
        if     (t == 0) f >> a >> b,      arb.update(a, b);
        else if(t == 1) f >> a >> b, g << arb.query(a, b) << '\n';
        else            f >> a     , g << arb.cbin(a) << '\n'; }
    return 0; }