#include <stdio.h>

int A[100001],B[100001],C[16],D[100001],i,j,m,n,p1,p2,S,k,x;

int k2c(int x)
{
int r = 0;
while (x%2==0)
{
r++;
x/=2;
}
return r;
}

int sum(int p)
{
int S=0;
while (p>0)
{
S = S+A[p];
p = p-C[D[p]];
}
return S;
}

int min(int st,int dr)
{
int m,b;
if (st>dr) return -1;
else {
     m = (st+dr)/2;
     b = sum(m);
     if (b>S) return min(st,m-1);
     else if (b<S) return min(m+1,dr);
     else return m;
     }
}

int main()
{
freopen("aib.in","r",stdin);
freopen("aib.out","w",stdout);

C[0]=1;
for (i=1;i<=16;i++) C[i] = C[i-1]*2;

scanf("%d%d",&n,&m);

for (i=1;i<=n;i++)
if (i%2==0) D[i] = k2c(i);
else D[i] = 0;

for (i=1;i<=n;i++) scanf("%d",&B[i]);

for (i=1;i<=n;i++)
{
A[i] = B[i];
for (j=1;j<=C[D[i]]-1;j++) A[i] += B[i-j];
}

for (i=1;i<=m;i++)
{
scanf("%d",&x);
if (x==0) {
          scanf("%d%d",&p1,&p2);
          while (p1<=n)
          {
          A[p1] = A[p1]+p2;
          p1 = p1+C[D[p1]];
          }
          }
else if (x==1) {
               scanf("%d%d",&p1,&p2);
               printf("%d\n",sum(p2)-sum(p1-1));
               }
else {
     scanf("%d",&S);
     printf("%d\n",min(1,n));
     }
}
}