#include <fstream>
using namespace std;

const int kMaxN = 100005;

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

int v[kMaxN + 5], BITree[kMaxN + 5], n, m;

void Update(int pos, int val){
    int i;

    for(i = pos; i <= n; i += i & (-i)){
        BITree[i] += val;
    }

}

int Query(int pos){
    int i, ans = 0;

    for(i = pos; i > 0; i -= i & (-i)){
        ans += BITree[i];
    }

    return ans;
}

int Query_search(int val){
    int pw, step = 0;

    for(pw = (1 << 30); pw > 0; pw = pw >> 1){
        if((step ^ pw) <= n && BITree[step ^ pw] <= val){
            step ^= pw;
            val -= BITree[step];

            if(!val){
                return step;
            }
        }
    }

    return -1;

}

int main() {
    int i, x, op, a, b;

    fin >> n >> m;

    for(i = 1; i <= n; ++i){
        fin>>x;
        Update(i, x);
    }

    for(i = 1; i <= m; ++i){
        fin>> op >> a;

        if(op == 0){
            fin>>b;
            Update(a, b);
        }
        else if(op == 1){
            fin>>b;
            fout<< Query(b) - Query(a - 1) << "\n";
        }
        else{
            fout<<Query_search(a) << "\n";
        }

    }
    return 0;
}