#include<stdio.h>


int n;
int a[100003],aib[100003];



void update(int i,int val)
{
	while(i<=n)
	{
		aib[i]+=val;
		i+=((i^(i-1))+1)>>1;
	}
}




int query(int i)
{
	int val=0;
	if(i==1)
		return aib[1];
	while(i>1)
	{
		val+=aib[i];
		i-=((i^(i-1))+1)>>1;
	}
	return val;
}




int search(int k)
{
	int st=1,dr=n,med,last=0,x;
	while(st<=dr)
	{
		med=(st+dr)/2;
		x=query(med);
		if(x==k)
		{
			last=med;
			dr=med-1;
		}
		else
			if(x<k)
				st=med+1;
			else
				dr=med-1;
	}
	return last;
}





int main()
{
	freopen("aib.in","r",stdin);
	freopen("aib.out","w",stdout);
	int i,m,x,y,k;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;++i)
	{
		scanf("%d",&a[i]);
		update(i,a[i]);
	}
	for(i=1;i<=m;++i)
	{
		scanf("%d",&k);
		if(k==0)
		{
			scanf("%d%d",&x,&y);
			update(x,y);
		}
		else
			if(k==1)
			{
				scanf("%d%d",&x,&y);
				printf("%d\n",query(y)-query(x-1));
			}
			else
			{
				scanf("%d",&x);
				printf("%d\n",search(x));
			}
	}
	return 0;
}