#include<fstream>
using namespace std;

int a[100001],n,m,i,x,y,z;

void update(int k, int x)
{
	while (k<=n)
	{
		a[k]+=x;
		k=(k|(k-1))+1;
	}
}

int query(int k)
{
	long long s=0;
	while (k!=0)
	{
		s+=a[k];
		k=k&(k-1);
	}
	return s;
}

int search(int k)
{
	int p,u,m,v;
	p=1;u=n;
	while (p<=u)
	{
		m=(p+u)/2;
		v=query(m);
		if (k<v)
			u=m-1;
		else if (k>v)
			p=m+1;
		else return m;
	}
	return -1;
}

int main()
{
	ifstream f("aib.in");
	ofstream g("aib.out");
	f >> n >> m;
	for (i=1;i<=n;i++)
	{
		f >> x;
		update(i,x);
	}
	for (i=1;i<=m;i++)
	{
		f >> x >> y;
		if (x==0)
		{
			f >> z;
			update(y,z);
		}
		else if (x==1)
		{
			f >> z;
			g << query(z)-query(y-1);
		}
		else  g << search(y);
		if (x!=0) 
			g << "\n";
	}
	return 0;
}