#include<fstream>

using namespace std;

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

int x,y,z,t,i,n,AIB[100001];

void insert(int poz,int val)
{
	while (poz<=n)
	{
		AIB[poz]+=val;
		poz=poz+poz-((poz-1)&poz);
	}
}

int query(int poz)
{
	int s=0;
	while (poz)
	{
		s+=AIB[poz];
		poz=poz-(poz-((poz-1)&poz));
	}
	return s;
}

int cautbin(int st,int dr,int x)
{
	int m=(st+dr)/2;
	
	if (st>dr) return -1;
	if (query(m)==x) return m;
	
	if (query(m)>x) return cautbin(st,m-1,x);
		else return cautbin(m+1,dr,x);
}

int main()
{
	in>>n>>t;
	
	for (i=1;i<=n;i++)
	{
		in>>x;
		insert(i,x);
	}
	
	for (i=1;i<=t;i++)
	{
		in>>x;
		if (x==0)
		{
			in>>y>>z;
			insert(y,z);
		}
		else if (x==1)
		{
			in>>y>>z;
			out<<query(z)-query(y-1)<<'\n';
		}
		else
		{
			in>>y;
			out<<cautbin(1,n,y)<<'\n';
		}
	}
}