#include <bits/stdc++.h>
#define f(x) x&(-x)

using namespace std;
ifstream fin("aib.in");
ofstream fout("aib.out");
typedef long long ll;

ll n, q;
ll aib[100005];

void add(ll val, ll pos);
ll query(ll pos);
ll src(ll val);

int main()
{

    fin >> n >> q;
    for(ll i = 1; i <= n; ++i){
        ll x;
        fin >> x;

        add(x, i);
    }

    while(q--){
        ll task;
        fin >> task;

        if(!task){
            ll a, b;
            fin >> a >> b;

            add(b, a);
        }
        else if(task == 1){
            ll a, b;
            fin >> a >> b;

            fout << query(b) - query(a - 1) << "\n";
        }
        else{
            ll a;
            fin >> a;

            fout << src(a) << "\n";
        }
    }

    return 0;
}

void add(ll val, ll pos){
    for(ll i = pos; i <= n; i += f(i))
        aib[i] += val;
}

ll query(ll pos){
    ll ret = 0LL;

    for(ll i = pos; i; i -= f(i))
        ret += aib[i];

    return ret;
}

ll src(ll val){
    ll ret = 0, maxp = 1;
    for(; maxp < n; maxp <<= 1);

    for(; maxp; maxp >>= 1){
        if(maxp + ret > n) continue;

        if(aib[maxp + ret] <= val){
            ret += maxp;
            val -= aib[ret];

            if(!val) return ret;
        }

    }

    return -1LL;
}