#include <cstdio>
#define ub(x) x&(-x)

using namespace std;
int a,b,n,aib[100009],i,op,x,o;

void update(int x,int i)
{
    for(;i<=n;i+=ub(i))
    aib[i]+=x;

}

int Sum(int a,int b)
{
   int s=0,i;
   for(i=b;i>=1;i-=ub(i))
   s+=aib[i];
   for(i=a-1;i>=1;i-=ub(i))
   s-=aib[i];
   return s;

}

int cb(int a)
{
   int st=1,dr=n,mj;
   while(st<=dr)
   {
       mj=(st+dr)/2;int x=Sum(1,mj);
       if(x==a) return mj;
       else if(x<a) st=mj+1;
       else dr=mj-1;

   }
   return -1;


}

int main()
{
    freopen("aib.in","r",stdin);
    freopen("aib.out","w",stdout);

    scanf("%d%d",&n,&op);

    for(i=1;i<=n;++i)
    {
       scanf("%d",&x);
       update(x,i);
    }

    for(i=1;i<=op;++i)
    {
       scanf("%d%d",&o,&a);
       if(o==0 || o==1) scanf("%d",&b);
       if(o==0) update(b,a);
       if(o==1) printf("%d\n",Sum(a,b));
       if(o==2)
       printf("%d\n",cb(a));

    }



    return 0;
}