#include<stdio.h>
#include<iostream.h>
#include<fstream.h>
#define N 100001
long n,m,y,z,i,j,poz,step;
int x;
unsigned long long c[N],b[N],p,a[N];

unsigned long long put(long x,long n)
{if(n==0)
       return 1;
if(n%2==0)
       return put(x,n/2)*put(x,n/2);
else
       return x*put(x,(n-1)/2)*put(x,(n-1)/2);}

void modificare(unsigned long long c[N],long y,long z,long n)
{long i=y,poz=0,step;
for(step=1;step<=n;step<<=1);
step>>=1;
while(i<=n)
      {c[i]+=z;
      while((i&put(2,poz))==0)
             poz++;
      if(step%i==0)
             i<<=1;
      else
             i+=put(2,poz);
      poz++;}}
       
long pozitie(unsigned long long c[N],unsigned long long p,long n)
{long step,i=0,j;
unsigned long long k=p;
for(step=1;step<n;step<<=1);
step>>=1;
while((step!=0)&&(i<n))
       {j=i+step;
       if(k==c[j])
              return j;
       else
              if(k>c[j])
                      {i=j;
                      k-=c[j];}
       step>>=1;}
if(k!=0)
       return -1;
else
       return i;}

unsigned long long suma(unsigned long long c[N],long y,long z,long n)
{long j=y-1,i=z,poz=0,k=0;
unsigned long long s1=0,s2=0;
for(step=1;step<=n;step<<=1);
step>>=1;
if(step%i==0)
       k=1;
while(i>0)
       {s1+=c[i];
       if(k==1)
             break;
       while((i&put(2,poz))==0)
             poz++;
       i-=put(2,poz);
       if(step%i==0)
             k=1;
       poz++;}
poz=0;
k=0;
if(step%j==0)
       k=1;
while(j>0)
       {s2+=c[j];
       if(k==1)
             break;
       while((j&put(2,poz))==0)
             poz++;
       j-=put(2,poz);
       if(step%j==0)
             k=1;
       poz++;}
return s1-s2;}

int main()
{fstream f1("aib.in",ios::in);
fstream f2("aib.out",ios::out);
f1>>n>>m;
b[0]=0;
for(i=1;i<=n;i++)
       {f1>>a[i];
       b[i]=b[i-1]+a[i];}
for(i=1;i<=n;i++)
       {j=i;
       poz=0;
       while((j&(put(2,poz)))==0)
              poz++;
       j=j-put(2,poz);
       c[i]=b[i]-b[j];}
for(i=1;i<=m;i++)
       {f1>>x;
       if(x==2)
              {f1>>p;
              f2<<pozitie(c,p,n)<<endl;}
       else
              if(x==0)
                      {f1>>y>>z;
                      modificare(c,y,z,n);}
              else
                      {f1>>y>>z;
                      if(y==z)
                              f2<<c[y]<<endl;
                      else
                              {for(step=1;step<=n;step<<=1);
                              step>>=1;
                              if(step%z==0)
                                    if(step%y==0)
                                           f2<<(c[z]-c[y])<<endl;
                                    else
                                           f2<<(c[z]-suma(c,1,y,n))<<endl;
                              else
                                    if(step%y==0)
                                           f2<<(suma(c,1,z,n)-c[y])<<endl;
                                    else
                                           f2<<suma(c,y,z,n)<<endl;}}}
f1.close();
f2.close();
return 0;}