#include <fstream>
#define DIM 100010
using namespace std;

int a[DIM];
int n, x, p, q, k, i, t, op;

int lsb(int x) {
    return x&-x;
}

void update(int i, int x) {
    for (;i<=n;i+=lsb(i))
        a[i]+=x;
}

int query(int i) {
    int s = 0;
    for (;i!=0;i-=lsb(i))
        s+=a[i];
    return s;
}

int query2(int k) {
    int p = 1, x;
    while(p*2 <= n)
        p*=2;
    i = p;

    for (;p;p/=2) {
        if (k==0)
            break;
        if ((x = query(i)) > k)
            i-=p/2;
        else {
            k -= x;
            i+=p/2;
        }
    }

    return i-p;
}

int main() {
    ifstream fin("aib.in");
    ofstream fout("aib.out");
    fin>>n>>t;
    for (i=1;i<=n;i++) {
        fin>>x;
        update(i, x);
    }

    for (;t;t--) {
        fin>>op;
        if (op == 0) {
            fin>>p>>x;
            update(p,x);
        } else
            if (op == 1) {
                fin>>p>>q;
                fout<<query(q) - query(p-1)<<"\n";
            } else {
                fin>>k;
                fout<<query2(k)<<"\n";
            }
    }

    return 0;
}