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

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

ll N,M,A[100005],a,b,type,aib[100005];
ll i,j,k;

void update(ll poz,ll val) {
    for (; poz <= N ; poz += (poz & (-poz)))
        aib[poz] += val;
}

ll query(ll poz) {
    if (poz == 0)
        return 0;
    ll rez = 0;

    for (; poz ; poz -= (poz & (-poz)))
        rez += aib[poz];

    return rez;
}

ll sum(ll a,ll b){
    return query(b) - query(a-1);
}

pair<ll,ll> query_max(ll a) {
    ll poz = 0;
    ll sum = 0;
    for (ll bit = 30;bit >= 0;bit--){
        if (((1 << bit) | poz) > N)
            continue;
        if (sum + aib[poz | (1 << bit)] <= a){
            poz |= (1 << bit);
            sum += aib[poz];
        }
    }

    return {poz,sum};
}

int main() {
    fin >> N >> M;

    for (i = 1;i <= N;i++){
        fin >> A[i];
        update(i,A[i]);
    }

    for (i = 1;i <= M;i++){
        fin >> type;
        if (type == 0) {
            fin >> a >> b;
            update(a,b);
        }
        else if (type == 1) {
            fin >> a >> b;
            fout << sum(a,b) << "\n";
        }
        else {
            fin >> a;
            pair<ll,ll> rez = query_max(a);
            if (rez.second == a)
                fout << rez.first << "\n";
            else
                fout << "-1\n";
        }
    }
}