#include <stdio.h>
#define nmax 100001
#define get2k(x) (x&(-x))

int aib[nmax],n,m,i,j,k,p;


void up(int pos,int x)
{
  for (;pos<=n;pos+=get2k(pos))
  	aib[pos]+=x;
}

int q(int pos)
{
  int sol=0;
  for (;pos;pos-=get2k(pos))
  	sol+=aib[pos];
  return sol;
}

int sr(int x)
{
	int pp=p; int i=n;
	while (pp)
	{
       if (i-pp>0)
       {
         int qr=q(i-pp);
         if (qr>=x) i-=pp;
       }
       pp/=2;
	}
 if (q(i)==x) return i;
  return -1;
}

int main()
{
   freopen("aib.in","r",stdin);
   freopen("aib.out","w",stdout);
  scanf("%d%d",&n,&m);
  for (i=1;i<=n;i++)
  {
  	scanf("%d",&k);
  	up(i,k);
  }
   p=1;
  while (p<=n) p*=2;

   while (m--)
   {
   	scanf("%d",&k);
   	 if (k==0)
   	 	  {
   	 	  	 scanf("%d%d",&i,&j);
              up(i,j);
   	 	  } else
   	 	 if (k==1)
   	 	   {
             scanf("%d%d",&i,&j);
             printf("%d\n",q(j)-q(i-1));

   	 	   } else
   	 	    {
   	 	     scanf("%d",&i);
              printf("%d\n",sr(i));
   	 	    }
   }

	return 0;
}