#include <fstream>

using namespace std;

int arb[100002];
int N,M;

inline void update (int ind, int x){

	int poz = 0; // pozitia initiala a celui mai nesemnificativ bit egal cu 1
				 // 2^poz = 1 => cel mai nesemnificativ bit va fi 1
	
	while (ind <= N) {
		arb[ind] += x;
		
		//while ( ! (ind & (1<<poz))  ) poz++; // se creste puterea lui 2, adica se trece bit-ul egal cu 1 prin toate pozitiile
											 // pana cand se intalneste primul bit egal cu 1 a lui ind, astfel se stie cati
											 // biti egali cu zero sunt la inceputul lui ind.
				
		//ind = ind + (1<<poz); // se aduna la ind numarul de biti egali cu 0 a lui ind pentru a forma noul indice.	
		//poz++; // daca ind este impar (doar la inceput este posibil, atunci atribuind 2^0 va avea un zero in plus.
			   // daca ind este par atunci din nou numarul de 0-uri creste cel putin cu 1.
	
		//new 
		poz = (ind ^ (ind-1)) & ind;
		ind = ind + poz;
	}

}

inline int query (int ind) {
	int s = 0, poz = 0;;
	
	while ( ind > 0) {
		
		s += arb[ind];
		
		poz = (ind ^ (ind-1)) & ind;

		ind = ind - poz;
	
			
	}	
	
	return s;
}

inline int search (int sum) {

	int st = 1, dr = N, mij, s, k = -1;
	
	while (st <= dr) {
	
		mij = (st+dr) >> 1;
		
		s = query(mij);
		
		if ( sum < s) dr = mij-1;
		else 
			if ( sum > s) st = mij + 1;
			else {
				k = mij; // salvam k
				dr = mij - 1; // mergem in partea stanga deoarece cautam un index prim care sa aiba valoarea Sum, 
							  // iar acest lucru se intampla doar in 
			
			}
	
	}
	return k;
}

int main(){
	
	int a,b,x;
	
	ifstream fin("aib.in");
	ofstream fout("aib.out");
	
	fin>>N>>M;
	
	for (int i = 1; i<= N; i++){
		fin >> x;
		update(i, x);
	}
	
	for ( ; M; M--){
	
		fin >> x;
		
		if ( x == 0) {
			fin>>a>>b;
			
			update(a, b);
		}
		
		if (x == 1) {
			fin >> a >> b;
			
			fout << query(b) - query(a-1) << "\n";
		
		}
		
		if (x == 2) {
		
			fin >> a;
			
			fout << search(a) << "\n";
			
		}
		
		
	}
			
	
	
	return 0;
}