#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 C = 0;
	while ( !(x & (1<<C)) ) C++;
	return C;
};


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

void operatie_0(int a, int b){
	int poz = a;
	while (poz <= n){
		arb[poz] += b;
		poz +=  1 << 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, s;
	st = 1, dr = n;
	
	while (st <= dr){
		mij = (st + dr) >> 1;
		s = suma_2(mij);

		if (s == a) return mij;
		if (s > a) dr = mij - 1;
		if (s < 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";
		};
	}
};