#include <stdio.h>
using namespace std;

FILE *fi=fopen("aib.in","r"),*fo=fopen("aib.out","w");

long n,m,i,j,a[1000000],x,y,op;

void aduna(long poz,long val){
	long z=0;
	a[poz]+=val;
	while (poz<=n){
		while (!(poz & 1<<z)) z++;
		poz+=1<<z;
		a[poz]+=val; 
	}	
}

long getval(long x){
	long aux=0,z=0;
	while (x){
		aux+=a[x];
		while (!(x & 1<<z)) z++;
		x-=1<<z; z=0;
	}
	return aux;
}

long suma(long st,long dr){
	return (getval(dr)-getval(st-1));
}

long caut(long x,long l,long r){
	long mid=(l+r)/2;
	if (l==r){
		if (suma(1,r)==x) return r; else return -1;
	}else{
		if (suma(1,mid)>=x) return caut(x,l,mid); else return caut(x,mid+1,r);
	}
	return 1;
}

int main(){
	fscanf(fi,"%ld%ld",&n,&m);
	for (i=1; i<=n; i++) {
		fscanf(fi,"%ld",&x);
		aduna(i,x);
	}
		
	for (i=0; i<m; i++){
		fscanf(fi,"%ld",&op);
		switch (op){
			case 0: fscanf(fi,"%ld%ld",&x,&y); aduna(x,y); break;
			case 1: fscanf(fi,"%ld%ld",&x,&y); fprintf(fo,"%ld\n",suma(x,y));break;
			case 2: fscanf(fi,"%ld",&x); fprintf(fo,"%ld\n",caut(x,1,n)); break;
		}
	} 
	
	fclose(fi); fclose(fo); return 0;
}