#include <fstream>
#include <math.h>
#define MaxN 100001
using namespace std;
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 = x >> 1;
	}
	return count;
};

int put(int x){
	int rez = 1;
	for (int i = 1; i <= x; ++i)
		rez = rez << 1;
	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){
	int st, dr, mij;
	st = 1, dr = n;
	
	while (st <= dr){
		mij = (st + dr) >> 1;
		if (suma_2(mij) == a) 
			return mij;
		if (suma_2(mij) > a) dr = mij - 1;
		if (suma_2(mij) < a) st = mij + 1;
	}
	return -1;
};

int main(){

	fin>>n>>m;
	int a, b, x;
	for (int i = 1; i <= n; i++){
		fin>>x;
		operatie_0(i, x);
	};
	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;
					fout<<operatie_2(a)<<"\n";
		};
	}
};