#include<fstream>
#include<cmath>
using namespace std;
long n,m,i,v[100001],op,a,b,nr,s[100001],x,mij,aux;
short zero(long x)
{short nr=0;
	while(x%2==0){ nr++; x/=2;}
	return nr;
}
long put(short x,short p)
{long rez=x,i;
   if(p==0)return 1;
	for(i=2;i<=p;i++)
		rez*=x;
	return rez;
}
void modifica(long poz,long val)//elementului de pe pozitia a i se va adauga valoarea b
{short i,nr=0;
	for(i=poz;i<=n;i+=nr)
	{
		v[i]+=val;
		nr=powl(2,zero(i));
	}
}
long calculeaza(long pozf)
{long i,nr=0,S=0;
	for(i=pozf;i>0;i-=nr)
	{
		nr=powl(2,zero(i));
		S+=v[i];
	}
	return S;
}
int search(int a,int p,int u)
{
	mij=(p+u)/2;
	while(p<=u)
	{    mij=(p+u+1)/2;
	      x=calculeaza(mij);
		if(x<a) p=(p+u)/2; 
		  else               
		if(x>a) u=(p+u)/2;
		  else return mij;
	}
}
int main()
{
	ifstream f("aib.in");ofstream g("aib.out");
	f>>n>>m;
	for(i=1;i<=n;i++)
	{ 
	  f>>x; 
	  s[i]=s[i-1]+x; 
	  v[i]=s[i]-s[i-put(2,zero(i))];//v[i] retine suma de la <i-2^k+1,i>,unde k=nr de o finale in reprezent binara a lui 
	}
	for(i=1;i<=m;i++)
	{
		f>>op;
		if(op<2)f>>a>>b;
		else f>>a;
		if(op==0)modifica(a,b);
		if(op==1)g<<calculeaza(b)-calculeaza(a-1)<<"\n";
		if(op==2)g<<search(a,1,n)<<"\n";
	}
	f.close();g.close();
return 0;}