#include <cstdio>
using namespace std;
int a[1<<18],x,y,s,n,m,val,poz,i,c;
void update(int nod, int st, int sf)
{
	if(st==sf){a[nod]+=val;}
	else{
		int mij=(st+sf)/2;
		if(poz<=mij){update(2*nod,st,mij);}
		else{update(2*nod+1,mij+1,sf);}
		a[nod]=a[2*nod]+a[2*nod+1];
		}
}
void query(int nod, int st, int sf)
{
	if((st>=x)&&(y>=sf)){s+=a[nod];}
	else{
		int mij=(st+sf)/2;
		if(x<=mij){query(2*nod,st,mij);}
		if(mij<y){query(2*nod+1,mij+1,sf);}
		}
}
void search(int st, int sf)
{
	y=(st+sf)/2;
	s=0;query(1,1,n);
	if(s==val){return;}
	if(st==sf){
		y=-1;
		return;
			  }
	if(s>=val){search(st,y);return;}
	else{search(y+1,sf);return;}
}
int main()
{
	freopen("aib.in","r",stdin);
	freopen("aib.out","w",stdout);
	scanf("%ld%ld",&n,&m);
	for(i=1;i<=n;i++){
		scanf("%ld",&val);poz=i;update(1,1,n);
					 }
	while(m--){
		scanf("%d",&c);
		if(c==0){
			scanf("%ld%ld",&poz,&val);
			update(1,1,n);
				}
		if(c==1){
			scanf("%ld%ld",&x,&y);
			s=0;query(1,1,n);
			printf("%ld\n",s);
				}
		if(c==2){
			scanf("%ld",&val);
			x=1;search(1,n);
			printf("%ld\n",y);
				}
			  }
return 0;
}