#include <cstdio>
#include <cstring>


#define file_in "aib.in"
#define file_out "aib.out"

#define lsb(x) ((x)&(-(x)))

#define nmax 101000

int N,M;
int tip,k,poz,val,a,b,X;
int Aib[nmax];

void add(int poz, int val){
	int i;
	for (i=poz;i<=N;i+=lsb(i))
		 Aib[i]+=val;
}

int sol(int poz){
	
	int i,ans=0;
	for (i=poz;i>=1;i-=lsb(i))
		 ans+=Aib[i];
	return ans;
}

int cauta(int k){
	
	int i,step;
	
	for (step=1;step<=N;step<<=1);
	for (i=0;step;step>>=1)
		 if (i+step<=N)
			 if (k>=Aib[i+step]){
				 k-=Aib[i+step];
				 i+=step;
				 if (k==0)
					 return i;
			 }
	return -1;
}	
	

int main(){
	
	int i;
	
	freopen(file_in,"r",stdin);
	freopen(file_out,"w",stdout);
	
	scanf("%d %d", &N, &M);
	for (i=1;i<=N;++i){
		scanf("%d", &X);
		add(i,X);
	}
	while(M--){
		scanf("%d", &tip);
		if (tip==0){
			scanf("%d %d", &poz,&val);
			add(poz,val);
		}
		else
		if (tip==1){
			scanf("%d %d", &a, &b);
			printf("%d\n", sol(b)-sol(a-1));
		}
		else
		if (tip==2){
			scanf("%d", &k);
			printf("%d\n", cauta(k));
		}
	}
	
	return 0;
}