#include<fstream>
#include<cstdio>
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=1;i<=n;i++)
	{
		aux=i;
		k=0;
		while(aux%2==0)
		{
			k++;
			aux=(aux>>1);
		}
		bit[i]=k;
	}
}

int main()
{
	int i,x,op,a,b;
	freopen("aib.in","r",stdin);
	scanf("%d %d",&n,&m);
	Precalculare();
	for(i=1;i<=n;i++)
	{
		scanf("%d",&x);
		Aduna(i,x);
	}
	freopen("aib.out","w",stdout);
	for(i=1;i<=m;i++)
	{
		scanf("%d",&op);
		if(op==0)
		{
			scanf("%d %d",&a,&b);
			Aduna(a,b);
			continue;
		}
		if(op==1)
		{
			scanf("%d %d",&a,&b);
			x=Suma(b)-Suma(a-1);
			printf("%d\n",x);
			continue;
		}
		if(op==2)
		{
			scanf("%d",&a);
			x=CautareBinara(a);
			printf("%d\n",x);
		}
	}
	return 0;
}