#include <bits/stdc++.h>
using namespace std;
const int NMAX = 1e5+2;
int n,m,t,a,b,aib[NMAX];

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

int query(int pos){
    int ans = 0;
    for(int i = pos; i > 0; i -= (i&-i)){
        ans += aib[i];
    }
    return ans;
}

void update(int pos, int val){
    for(int i = pos; i <= n; i += (i&-i)){
        aib[i] += val;
    }
}

int range(int st, int dr){
    return query(dr)-query(st-1);
}

int kth(int k){
    int pas = (1<<(__lg(n)+1));
    int pos = 0;
    while(pas){
        if(pas + pos <= n){
            if(k >= aib[pas+pos]){
                pos += pas;
                k -= aib[pos];
                if(k == 0){
                    return pos;
                }
            }
        }
        pas /= 2;
    }
    return -1;
}

int main()
{
    fin >> n >> m;
    for(int i = 1; i <= n; i++){
        int x;
        fin >> x;
        update(i, x);
    }
    while(m--){
        fin >> t;
        if(t == 0){
            fin >> a >> b;
            update(a, b);
        }else if(t == 1){
            fin >> a >> b;
            fout << range(a, b) << "\n";
        }else{
            fin >> a;
            fout << kth(a) << "\n";
        }
    }
    return 0;
}