#include <fstream>
#define dim 100010
using namespace std;
int a[dim];
int v[dim];
int i,n,q,t,poz,val,x,y;

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

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

int query (int x) { ///returneaza suma valorilor de la 1 la x
    int s=0;
    for (int i=x;i>0;i-=lsb(i)) {
        s+=a[i];
    }
    return s;
}

int main() {
    ifstream fin("aib.in");
    ofstream fout("aib.out");
    fin>>n>>q;
    for (i=1;i<=n;i++) {
        fin>>v[i];
        update(i,v[i]);
    }
    for (;q--;) {
        fin>>t;
        if (t==0) {
            fin>>poz>>val;
            update(poz,val);
        }
        if (t==1) {
            fin>>x>>y;///suma val din intervalul [a,b]
            fout<<query(y)-query(x-1)<<"\n";
        }
        if (t==2) {
            fin>>val;///k a.i. query(k)=a
            int st=1;
            int dr=n;
            while (st<=dr) {
                int mid=(st+dr)/2;
                if (query(mid)>=val) {
                    dr=mid-1;
                }
                else {
                    st=mid+1;
                }
            }
            fout<<st<<"\n";
        }
    }
  /*  for (i=1;i<=n;i++) {
        fout<<v[i]<<" ";
    }
    fout<<"\n";
    for (i=1;i<=n;i++) {
        fout<<a[i]<<" ";
    }
    fout<<"\n"; */
    return 0;
}