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

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

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

long long query (long long x) { ///returneaza suma valorilor de la 1 la x
    long long s=0;
    for (long long 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 long longervalul [a,b]
            fout<<query(y)-query(x-1)<<"\n";
        }
        if (t==2) {
            fin>>val;///k a.i. query(k)=a
            long long st=1;
            long long dr=n;
            while (st<=dr) {
                long long 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;
}