#include <cstdio>
#define wmax 100001
using namespace std;
unsigned int abi[wmax];
unsigned int n;
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;
}
unsigned int poz(int x)
{
    int i=0,interval=n/2;
    while (interval)
    {
        if (abi[i+interval]<x)
        {
            x-=abi[i+interval];
            i+=interval;
        }
        interval/=2;
    }
    return i;
}
int main()
{
    FILE *f,*g;
    f=freopen("aib.in","r",stdin);
    g=freopen("aib.out","w",stdout);

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

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