#include <cstdio>
#define N 100005
using namespace std;
int n,m,i,x,y,c,v[N],Step,sum(int),pos(int);
void add(int,int);
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",&x);
        add(x,i);
    }
    for(Step=1;Step<=n;Step<<=1);Step<<=1;
    for(;m;m--)
    {
        scanf("%d%d",&c,&x);
        if(c==0)
        {
            scanf("%d",&y);
            add(y,x);
        }
        else
        if(c==1)
        {
            scanf("%d",&y);
            printf("%d\n",sum(y)-sum(x-1));
        }
        else
        {
            printf("%d\n",pos(x));
        }

    }
    return 0;
}
void add(int val,int poz)
{
    for(;poz<=n;poz+=poz&(-poz))v[poz]+=val;
}
int sum(int poz)
{
    int ret=0;
    for(;poz;poz-=poz&(-poz))ret+=v[poz];
    return ret;
}
int pos(int val)
{
    int poz=0,step=Step;

    for(;step;step>>=1)
        if(v[poz+step])
            if(v[poz+step]<=val)
            {
                poz+=step;
                val-=v[poz];
            }
    return val?0:poz;
}