#include<fstream>
#define MAX 100001
using namespace std;
int AIB[MAX],N,M;
int bit(int x)
{
	return (x&(x-1))^x;
}
void update(int a,int b)
{
	int i;
	for(i = a;i<=N;i+=bit(i))
		AIB[i] += b;
}
int querry(int a)
{
	int i,s = 0;
	for(i = a;i>=1;i-=bit(i))
		s+=AIB[i];
	return s;
}
int cautbin(int a)
{
	int l = 1, r = N,mid,aux;
	while(l<=r)
	{
		mid = l + (r-l)/2;
		aux = querry(mid);
		if(aux == a)return mid;
		if(aux < a)l = mid+1;
		else r = mid-1;
	}
	return -1;
}
int main()
{
	ifstream f("aib.in");
	f>>N>>M;
	int i,x,a,b;
	for(i=1;i<=N;++i)
	{
		f>>x;
		update(i,x);
	}
	ofstream g("aib.out");
	//g<<querry(1)<<"\n";
	while(M--)
	{
		f>>x;
		if(!x)
		{
			f>>a>>b;
			update(a,b);
		}
		if(x == 1)
		{
			f>>a>>b;
			g<<querry(b)-querry(a-1)<<"\n";
		}
		if(x==2)
		{
			f>>a;
			g<<cautbin(a)<<"\n";
		}
	}
	f.close();
	g.close();
	return 0;
}