#include<cstdio>
int n,i,j,a,b,m,s[100001];
inline void add(int x,int y)
{
	int k=1;
	while((x&k)==0) k<<=1;
	s[x]+=y;
	while(x+k<=n)
	{
		x=x+k;
		s[x]+=y;
		while((x&k)==0) k<<=1;
	}
}
inline int get(int x)
{
	if(x==0) return 0;
	int k=1,sum;
	while((x&k)==0) k<<=1;
	sum=s[x];
	while(x-k>0)
	{
		x=x-k;
		sum+=s[x];
		while((x&k)==0) k<<=1;
	}
	return sum;
}
int search(int st,int dr,int x)
{
	/*
	if(st==dr) 
		if(get(st)==x)
			return st;
		else return -1;
	int mij=(st+dr)>>1,k;
	k=get(mij);
	if(k<x) return search(mij+1,dr,x);
	else
		if(k==x)
		{
			k=search(st,mij-1,x);
			if(k!=-1) return k;
			else
				return mij;
		}
		else
			return search(st,mij-1,x);
			*/
	return -1;
}
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",&a);
		add(i,a);
	}
	for(i=1;i<=m;i++)
	{
		scanf("%d %d",&j,&a);
		if(j<2) scanf("%d",&b);
		switch(j)
		{
		case 0: add(a,b);break;
		case 1: printf("%d\n",get(b)-get(a-1));break;
		case 2: printf("%d\n",search(1,n,a));break;
		}
	}
	fclose(stdout);
	return 0;
}