#include<fstream>
#define MaxN 100005
#define MaxM 150005
#define bit(x) ((x^(x-1))&x)

using namespace std;

ifstream fin("aib.in");
ofstream fout("aib.out");

int arb[MaxN],n,m;

void add(int x, int v)//arb[x]+=v;
{	for(;x<=n;x+=bit(x))arb[x]+=v;}

int query(int x)//suma de la 1 la x
{	int s=0;
	for(;x;x-=bit(x))s+=arb[x];
	return s;
}

int bsearch(int a) //calculul sumei primilor k termeni
{	int m,st,dr,q;
	st=1;dr=n;
	while(st<=dr)
	{	m=(st+dr)/2;
		q=query(m);
		if(q==a)
		{	if(query(m-1)==a) dr=m-1;
			return m;
		}
		else	if(q<a) st=m+1;
				else	dr=m-1;
	}
	return -1;
}
	
int main()
{	int i,op,val,a,b;
	fin>>n>>m;
	for(i=1;i<=n;++i)
	{	fin>>val;
		add(i,val);
	}
	for(i=1;i<=m;++i)
	{	fin>>op;
		if(op==0)
		{	fin>>a>>b;
			add(a,b);
		}
		if(op==1)
		{	fin>>a>>b;
			fout<<query(b)-query(a-1)<<'\n';
		}
		if(op==2)
		{	fin>>a;
			fout<<bsearch(a)<<'\n';
		}
	}
	return 0;
}