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

using namespace std;
int a[100009],i,x,y,n,k,caz;

int suma(int poz)
{
    int i,sum=0;
    for(i=poz; i>0; i-=ub(i))
        sum+=a[i];

    return sum;

}

int cb(int x)
{
   int mij,st=1,dr=n,sol;

   while(st<=dr)
   {
      mij=(st+dr)/2;
      sol=suma(mij);
      if(sol==x) return mij;
      else if(sol<x) st=mij+1;
      else dr=mij-1;
   }

   return -1;

}

void update(int v,int p)
{
    int i;
    for(i=p; i<=n; i+=ub(i))
        a[i]+=v;

}

int S(int p1,int p2)
{

    return suma(p2)-suma(p1-1);
}

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

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

    for(i=1; i<=n; ++i)
    {
        scanf("%d",&x);
        update(x,i);
    }
int ii;
    for(ii=1; ii<=k; ++ii)
    {
        scanf("%d%d",&caz,&x);
        if(caz!=2) scanf("%d",&y);

        if(caz==0)
        {
            for(i=x; i<=n; i+=ub(i))
                a[i]+=y;

        }
        else if(caz==1)
            printf("%d\n",S(x,y));

        else
            printf("%d\n",cb(x));



    }








    return 0;
}