#include<cstdio>
#include<algorithm>
using namespace std;
int n,i,j,k,m,a,b,x,v[100005],s[100005],y,mij;
int slb(int x)
{return x & -x; }
void update(int x,int y)
{
	for (;x<=n;x+=slb(x)) 
		s[x]+=y;
}
int query(int x)
{
	int sum=0;
	for (;x>=1;x-=slb(x))
		sum+=s[x];
	return sum;
}
void bin(int st,int dr,long long x)
{
	mij=(st+dr)/2;
	int p=query(mij);
	if (p==x) return;else
		if (p>=x) bin(st,mij,x);else
			bin(mij+1,dr,x);
}

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