#include<cstdio>

int N,M;
int c[150000];

void insert(int x,int y){
	int nr=0;
	while(x<=N){
		c[x]+=y;
		while(!(x&(1<<nr))){
			nr++;
		}
		x+=(1<<nr);
		nr++;
	}
}

int sum(int x){
	int nr=0;
	int suma=0;
	while(x>0){
		suma+=c[x];
		while(!(x&(1<<nr))){
			nr++;
		}
		x-=(1<<nr);
		nr++;
	}
	return suma;
}

int min(int k){
	int i=0;
	int step;
	// cea mai mare putere a lui 2 
	for(step=1;step<N;step<<=1);
	// fiecare putere a lui 2 pana in valoarea maxima
	for(i;step;step>>=1){
		if(i+step<=N){
			if(k>=c[i+step]){
				i+=step;
				k-=c[i];
				if(k==0) return i;
			}
		}
	}
	return -1;
}

int main(){
	int t,x,y;
	freopen("aib.in","r",stdin);
	freopen("aib.out","w",stdout);

	scanf("%d %d",&N,&M);
	for(int i=1;i<=N;i++) {
		scanf("%d",&t);
		insert(i,t);
	}

	for(;M--;){
		scanf("%d",&t);
		if(t==0){
			scanf("%d %d",&x,&y);
			insert(x,y);
		}else
		if(t==1){
			scanf("%d %d",&x,&y);
			printf("%d\n",sum(y)-sum(x-1));
		}else
		if(t==2){
			scanf("%d",&x);
			printf("%d\n",min(x));
		}

	}
	return 0;
}