#include <cstdio>

int a[15001],v[15001],y[40],n=0,m=0;

int asd(int nr)
{
    int s=0,s1=0,i=0;
    if (nr==0)
        return 0;
    else
    {
        for (i=0; i<40; ++i) y[i]=0;
        i=0;
        while (nr>0)
        {
            y[i++]=nr%2;
            nr/=2;
        }
        nr=i;
        for (i=nr-1; i>=0; --i)
        {
            s1=s1+y[i]*(1<<i);
            if (y[i]==1)
                s+=a[s1];
        }
        return s;
    }
}

int upd(int p,int q)
{
    int k=p;
    while (k<n+1)
    {
        if (q<=a[k])
            a[k]-=q;
        else
            a[k]=0;
        k=2*k-(k&(k-1));
    }
    return 0;
}

int main()
{
    int i=0,x=0,p=0,q=0,k=0,s=0,nr=0,j=0;
    freopen("datorii.in","r",stdin);
    freopen("datorii.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (i=1; i<=n; ++i)
        scanf("%d",&v[i]);
    a[1]=v[1];
    for (i=2; i<n+1; ++i)
    {
        a[i]=v[i];
        s=0;
        for (j=0; j<40; ++j) y[j]=0;
        j=0;
        nr=i;
        while (nr>0)
        {
            y[j++]=nr%2;
            nr/=2;
        }
        nr=j;
        for (j=nr-1; j>=0; --j)
        {
            s=s+y[j]*(1<<j);
            if (y[j]==1)
                a[i]+=a[s];
        }
    }
    a[1]=1;
    a[2]=4;
    a[3]=2;
    a[4]=6;
    a[5]=0;
    a[6]=10;
    for (i=1; i<m+1; ++i)
    {
        scanf("%d%d%d",&x,&p,&q);
        if (x==1)
            printf("%d\n",asd(q)-asd(p-1));
        else upd(p,q);
    }
    return 0;
}