#include<fstream>
using namespace std;
int n,m,v[100010];
short bit[100010];

inline void Aduna(int poz,int x)
{
	while(poz<=n)
	{
		v[poz]+=x;
		poz=poz+(1<<bit[poz]);
	}
}

inline int Suma(int poz)
{
	int sum=0;
	while(poz)
	{
		sum+=v[poz];
		poz=poz-(1<<bit[poz]);
	}
	return sum;
}

inline int CautareBinara(int S)
{
	int st,dr,m,sum;
	st=1;
	dr=n;
	while(st<=dr)
	{
		m=(st+dr)/2;
		sum=Suma(m);
		if(sum==S)
			return m;
		if(sum<S)
			st=m+1;
		else
			dr=m-1;
	}
	return -1;
}

inline void Precalculare()
{
	int i,aux,k;
	for(i=2;i<=n;i+=2)
	{
		aux=i;
		k=0;
		while(aux%2==0)
		{
			k++;
			aux=(aux>>1);
		}
		bit[i]=k;
	}
}

int main()
{
	int i,x,op,a,b;
	ifstream fin("aib.in");
	fin>>n>>m;
	Precalculare();
	for(i=1;i<=n;i++)
	{
		fin>>x;
		Aduna(i,x);
	}
	ofstream fout("aib.out");
	for(i=1;i<=m;i++)
	{
		fin>>op;
		if(op==0)
		{
			fin>>a>>b;
			Aduna(a,b);
			continue;
		}
		if(op==1)
		{
			fin>>a>>b;
			x=Suma(b)-Suma(a-1);
			fout<<x<<"\n";
			continue;
		}
		if(op==2)
		{
			fin>>a;
			x=CautareBinara(a);
			fout<<x<<"\n";
		}
	}
	fin.close();
	fout.close();
	return 0;
}