# include <fstream>
using namespace std;
ifstream f ("aib.in");
ofstream g ("aib.out");
int a[100005],x,i,n,m,q,w;

 void adauga (int i,int x)
 {
	 int k,l;
	  while (i<=n)
	 {
	 k=i;
	 l=1;
	 a[i]+=x;
	 while (k%2==0)
		{ 
			l*=2;
			k=k/2;
	    }
	 
	
		 
		 i+=l;
	 }
 }

 int sum (int i)
 {
	
	int k,l,s=0;
	  while (i>0)
	 {
	 k=i;
	 l=1;
	 s+=a[i];
	 while (k%2==0)
		{ 
			l*=2;
			k=k/2;
	    }
	 
	
		 
		 i-=l;
	 }
	 return s;
 }
 
 void cauta (int i,int j)
 {
	 int x;
	 while (i<=j)
	 {
		 w=(i+j)/2;
		 x=sum (w);
		 
		 if (x==q)
			 break;
		 else
			 if (q<x)
				 j=w-1;
			 else
				 i=w+1;
	 }
	 if (j<i)
		 w=-1;
 }
 

int main ()
{
	f>>n>>m;
	for (i=1;i<=n;i++)
	{
		f>>x;
		adauga (i,x);
	}
	
	for (i=1;i<=m;i++)
	{
		f>>x;
		if (x==0)
		{
			f>>q>>w;
			adauga (q,w);
		}
		if (x==1)
		{
			f>>q>>w;
			g<<sum (w)-sum (q-1)<<"\n";
		}
		if (x==2)
		{
			f>>q;
			w=0;
			cauta (1,n);
			g<<w<<"\n";
		}
	}
	return 0;
}