#include <iostream>
#include <cstdio>
using namespace std;

int n,m,aib[150100],x,tip,a,b;

int put (int nr)
{
    /*int rid=1;
    while (!(nr&1))
    {
        nr>>=1;
        rid<<=1;
    }
    return rid;
    */ ///ineficient asa
    return ((nr xor (nr-1)) & nr);
}

void update(int x,int i)
{
    while (i<=n)
    {
        aib[i]+=x;
        i+=put(i);
    }
}

int aflu_suma(int poz)
{
    int s=0;
    while (poz>0)
    {
        s+=aib[poz];
        poz-=put(poz);
    }
    return s;
}

void citire()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;++i)
    {
        scanf("%d",&x);
        update(x,i);
    }
}

int caut(int x)
{
    int st=1,dr=n;
    int mij=(st+dr)/2;
    while (st<=dr)
    {
        int s=aflu_suma(mij);
        if (s==x)
            return mij;
        if (s>x)
            dr=mij-1;
        else st=mij+1;
        mij=(st+dr)/2;
    }
    return -1;
}

void rezolv ()
{
    for (int i=1;i<=m;++i)
    {
        scanf("%d",&tip);
        if (tip<2)
        {
            scanf("%d%d",&a,&b);
            if (tip==0)

                update(b,a);

            else
            {
                int s=aflu_suma(b)-aflu_suma(a-1);
                printf("%d\n",s);
            }
        }
        else
        {
            scanf("%d",&x);
            printf("%d\n",caut(x));
        }
    }
}

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

    return 0;
}