#include <cstdio>
#define wmax 100001
using namespace std;
unsigned int abi[wmax];
unsigned int n,pmax;
void update(unsigned int val, unsigned int x)
{
    while (x<=n)
    {
        abi[x]+=val;
        x+= x & -x;
    }
}
unsigned int sum(unsigned int x,unsigned int y)
{
    unsigned int s1=0,s2=0;
    while (y)
    {
        s1+=abi[y];
        y=y&(y-1);
    }
    x--;
    while (x)
    {
        s2+=abi[x];
        x=x&(x-1);
    }
    return s1-s2;
}
int poz(int x)
{
    int i=0,interval=pmax/2;
    while (interval)
    {
        if (abi[i+interval]<=x&&(i+interval<=n))
        {
            x-=abi[i+interval];
            i+=interval;
            if (!x) return i;
        }
        interval/=2;
    }
    return -1;
}
int main()
{
    FILE *f,*g;
    f=freopen("aib.in","r",stdin);
    g=freopen("aib.out","w",stdout);

    unsigned int i,x,q,y,ok,p1=0;
    fscanf(f,"%u%u",&n,&q);
    for (i=1;i<=n;i++)
    {
        fscanf(f,"%u",&x);
        update(x,i);
    }
    for (pmax=1;pmax<=n;pmax<<=1);
    for (i=1;i<=q;i++)
    {
        fscanf(f,"%u%u",&ok,&x);
        if (ok==2)
        {
            p1++;
            fprintf(g,"%d\n",poz(x));
        }
        else
        {
            fscanf(f,"%u",&y);
            if (!ok) update(y,x);
            else fprintf(g,"%u\n",sum(x,y)),p1++;
        }

    }
    fclose(f);
    fclose(g);
    return 0;
}