#include <cstdio>
#include <climits>

using namespace std;

#define NMAX 10010
#define ub(x) (x&(-x))

int Aib[NMAX];

void Update(int V,int P)
{
    for (int i=P;i<NMAX;i+=ub(i))
    Aib[i]+=V;
}

int Sum(int P)
{
    int sol=0;

    for (int i=P;i>0;i-=ub(i))
    sol+=Aib[i];

    return sol;
}

int Query(int S)
{
    int L=1,R=NMAX,M=0,sol=-1,nowS=0;

    while (L<=R)
    {
        M=(L+R)/2;

        nowS=Sum(M);

        if (nowS==S)
        {
            sol=M;
            R=M-1;
            continue;
        }

        if (nowS<S)
        {
            L=M+1;
            continue;
        }

        R=M-1;
    }

    return sol;
}

void Read()
{
    int i,M,N,X,Y,type;

    scanf("%d%d",&N,&M);
    for (i=1;i<=N;++i)
    {
        scanf("%d",&X);
        Update(X,i);
    }

    while (M--)
    {
        scanf("%d",&type);

        if (type==0)
        {
            scanf("%d%d",&X,&Y);
            Update(Y,X);
            continue;
        }

        if (type==1)
        {
            scanf("%d%d",&X,&Y);
            printf("%d\n",Sum(Y)-Sum(X-1));
            continue;
        }

        scanf("%d",&X);
        printf("%d\n",Query(X));
    }

}

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

Read();

return 0;
}