#include <stdio.h>
#define dim 15000

int n, a[dim+1], x[dim+1];
long m;

void preproc()
{
	int i, k, s, j;
	for (i=1; i<=n; i++)
	{
		k=0;
		j=i;
		while (j%2==0) j/=2;
		k=i-i/j+1;
		s=0;
		for (j=k; j<=i; j++) s+=a[j];
		x[i]=s;
	}
}

long suma1(int p)
{
	long s=0;
	int t;
	while (p)
	{
		s+=x[p];
		t=p;
		while (t%2==0) t/=2;
		p-=p/t;
	}
	return s;
}

long suma(int st, int dr)
{
	return suma1(dr)-suma1(st-1);
}

void actualizeaza(int p, int val)
{
	int t;
	while (p<=n)
	{
		x[p]-=val;
		t=p;
		while (t%2==0) t/=2;
		p+=p/t;
	}
}

int main()
{
	int i, op, p1, p2;
	long j;
	freopen("datorii.in", "r", stdin);
	freopen("datorii.out", "w", stdout);
	scanf("%d %ld\n", &n, &m);
	for (i=1; i<=n; i++)
		scanf("%d ", &a[i]);
	preproc();
	for (j=0; j<m; j++)
	{
		scanf("%d %d %d\n", &op, &p1, &p2);
		if (op) printf("%ld\n", suma(p1, p2));
		else actualizeaza(p1, p2);
	}
	return 0;
}