#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)
{
	int mij,k;
	while(st<dr)
	{
		mij=(st+dr)>>1;
		k=get(mij);
		if(k==x) return mij;
		if(k<x)
			st=mij+1;
		else
			dr=mij-1;
	}
	if(get(st)==x) return st;
	else
		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;
}