#include <fstream>

using namespace std;
ifstream fin("aib.in");
ofstream fout("aib.out");
#define zeros(x) ((x) & (-x))

int AIB[100010],N,M,a,b,key;
void add(int x,int pos){
	for(pos; pos<=N;pos+=zeros(pos) ){
		AIB[pos]+=x;
	}
}

int query(int a, int b){
	int sum;
	for(b; b > 0;b -= zeros(b)){
		sum+=AIB[b];	
	}
	a--;
	for(a; a > 0;a -= zeros(a)){
		sum-=AIB[a];
	}
	return sum;
}
int tot = 0;
int find(int a){
	int mid, f,l,val;
	for(f = 1,l = N; f <= l;){
		mid = (f+l)/2;
		tot++;
		fout << "";
		val = query(1,mid);
		if(val == a) f = l+1; else if (val > a)l = mid; else f = mid+1; 
	}
	return mid;
}
int main(){
	fin >> N >> M;
	for(int i = 1;i <= N;i++){
		fin >> key;
		add(key,i);
	}
	for(int j = 0;j < M;j++){
		fin >> key;
		switch(key){
			case 0:{
				fin >> a >> b;
				add(b,a);
				break;
			}
			case 1:{
				fin >> a >> b;
				fout << query(a,b) << '\n';
				break;
			}
			case 2:{
				fin >> a;
				fout << find(a)<< '\n';
				break;
			}
		}
	}
	return 0;
}