#include <fstream>
#include <math.h>
#define MaxN 100001
using namespace std;
int v[MaxN];
int n, m, op;
int arb[MaxN];
fstream fin ("aib.in",  ios::in);
fstream fout("aib.out", ios::out);

int zero_t(int x){
	int count = 0;
	while (x % 2){
		++count;
		x /= 2;
	}
	return count;
};

int put(int x){
	int rez = 1;
	for (int i = 1; i <= x; ++i)
		rez *= 2;
	return rez;
};


int suma(int st, int dr){
	int rez = 0;
	for (int i = st; i <= dr; ++i)
		rez += v[i];
	return rez;
};

int suma_2(int poz){
	int rez = 0;
	while (poz > 0){
		rez += arb[poz];
		poz -= put ( zero_t(poz) ); 
	};
	return rez;
};

void operatie_0(int a, int b){
	int poz = a;
	while (poz <= n){
		arb[poz] += b;
		poz += put( zero_t(poz) );
	};
};

int operatie_1(int a, int b){

	return suma_2(b) - suma_2(a-1);

};

int operatie_2(int a){
	return 0;
};

int main(){

	fin>>n>>m;
	int a, b;
	for (int i = 1; i <= n; i++)
		fin>>v[i];
	for (int i = 1; i <= n; i++)
		arb[i] = suma(i - put(zero_t(i)) + 1, i);
	for (int i = 1; i <= m; i++){
		fin>>op;
		switch(op){
			case 0 :fin>>a>>b; 
					operatie_0(a, b);
					break;
			case 1 :fin>>a>>b;
					fout<<operatie_1(a, b)<<"\n";
					break;
			case 2 :fin>>a;
					operatie_2(a);
		};
	}
};