#include<fstream>
using namespace std;
ifstream F("aib.in");
ofstream G("aib.out");
int n,m,i,c[100001],b,j,k,s,t,l;
int main()
{
    for(F>>n>>m,i=1;i<=n;++i)
        for(F>>k,j=i;j<=n;c[j]+=k,j+=(j&(-j)));
    for(l=1;l<=n;l<<=1);
    for(;m--;)
        if(F>>b>>j,b==2) {
            for(i=0,k=l;k;k>>=1)
                if(i+k<=n&&j>=c[i+k])
                    j-=c[i+k],i+=k;
            G<<(j||!i?-1:i)<<'\n';
        } else if(F>>k,!b)
            for(;j<=n;c[j]+=k,j+=(j&(-j)));
        else {
            for(s=t=0;k;s+=c[k],k-=(k&(-k)));
            for(--j;j;t+=c[j],j-=(j&(-j)));
            G<<s-t<<'\n';
        }
    return 0;
}