#include <cstdio>
using namespace std;
int a[1<<17],n,m,i,poz,val,s,y,c,x;
void update()
{
	a[poz]+=val;
	int aux=poz,r=0;
	while((aux>>r)%2==0){r++;}
	poz+=1<<r;
	if(poz<=n){update();}
}
void query()
{
	s+=a[poz];
	int aux=poz,r=0;
	while((aux>>r)%2==0){r++;}
	poz-=1<<r;
	if(poz){query();}
}
void smartquery()
{
	poz=y;s=0;query();
	int s2=s;
	poz=x-1;
	s=0;
	if(poz){query();}
	s=s2-s;
}
void search(int st, int sf)
{
    y=(st+sf)/2;poz=y;
    s=0;query();
    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();
						   }
	while(m--){
		scanf("%d",&c);
		if(c==0){
			scanf("%ld%ld",&poz,&val);
			update();
				}
		if(c==1){
			scanf("%ld%ld",&x,&y);
			smartquery();
			printf("%ld\n",s);
				}
		if(c==2){
			scanf("%ld",&val);
			x=1;search(1,n);
			printf("%ld\n",y);
				}
			  }
return 0;
}