#include<stdio.h>
#define NMAX 100001
int n,a[NMAX],s[NMAX],v[NMAX],M;
int nr0(int x)
{
	int contor=0;
	while(x%2==0)
	{
		contor++;
		x>>=1;
	}
	return 1<<contor;
}
void op0(int poz,int val)
{
	  int C = 0;
     while ( poz <= n )
     {
           v[poz] += val;
           while ( !(poz & (1<<C)) ) C++;
           poz += (1<<C);
           C += 1;
     }
}
int  op1(int poz)
{
  int C = 0, S = 0;  
     while ( poz > 0 )  
    {  
           S += v[poz];  
          while ( !(poz & (1<<C)) ) C++;  
           poz -= (1<<C);  
           C += 1;  
    }  
       
     return S;  
}
int op2(int k)
{
	int st=1,dr=n,s,m;
	while(st<=dr)
	{
		m=(st+dr)/2;
		s=op1(m);
		if(k>s)
			st=m+1;
		else
			if(k<s)
				dr=m-1;
			else
				return m;
			
	}
	return -1;
}
int main()
{
	int i,x,y,z;
	freopen("aib.in","r",stdin);
	freopen("aib.out","w",stdout);
	scanf("%d%d",&n,&M);
	for(i=1;i<=n;i++)
	{
		scanf("%d",a+i);
		s[i]=s[i-1]+a[i];
	}

	for(i=1;i<=n;i++)
		v[i]=s[i]-s[i-nr0(i)];
	
	for(i=1;i<=M;i++)
	{
		scanf("%d",&x);
		if(x==0)
		{
			scanf("%d%d",&y,&z);
			op0(y,z);

		}
		else
			if(x==1)
			{
				scanf("%d%d",&y,&z);
				printf("%d\n",op1(z)-op1(y-1));
			}
			else
			{
				scanf("%d",&y);
				printf("%d\n",op2(y));
			}
	}

	return 0;
}