#include <cstdio>
#define Bsize 65536
#define ub(x) (x&(-x))
using namespace std;
char Buffer[Bsize];
int p,n,m,i,tip,a,b,x,y;
int AIB[100010],s,k,nr;

void add(int x,int y)
{
    int j;
    for(j=y; j<=n; j+=ub(j))
        AIB[j]+=x;
}

long long sum(int x)
{
    int j;
    long long s=0;
    for(j=x; j>0; j-=ub(j))
        s+=AIB[j];
    return s;
}

long long sum2(int a,int b)
{
    int j;
    long long s=0;
    s=sum(b)-sum(a-1);
    return s;
}

int verif(int k)
{
    int st,dr,mij;
    st=1;dr=n;
    while(st<=dr)
    {
        mij=st+(dr-st)/2;
        if(sum(mij)==k)
          return mij;
        if(sum(mij)>k)
          dr=mij-1;
          else st=mij+1;
    }
    return -1;

}
int number(int &p)
{
    nr=0;
    while(Buffer[p]<'0' || Buffer[p]>'9')
    {
        if(p==Bsize-1)
        {
            fread(Buffer,1,Bsize,stdin);
            p=0;
        }
        else ++p;
    }
    while(Buffer[p]>='0' && Buffer[p]<='9')
    {
        nr=nr*10+Buffer[p]-'0';
        if(p==Bsize-1)
        {
            fread(Buffer,1,Bsize,stdin);
            p=0;
        }
        else ++p;
    }
    return nr;

}

int main()
{
    freopen("aib.in","r",stdin);
    freopen("aib.out","w",stdout);
    fread(Buffer,1,Bsize,stdin);
    p=0;
    n=number(p);m=number(p);
    for(i=1;i<=n;++i)
    {
        x=number(p);
        add(x,i);
    }
    for(i=1;i<=m;++i)
    {
        tip=number(p);
        if(tip==0)
        {
            a=number(p);b=number(p);
            add(b,a);
        }
        if(tip==1)
        {
            a=number(p);b=number(p);
            s=sum2(a,b);
            printf("%d\n",s);
        }
        if(tip==2)
        {
            k=number(p);
            x=verif(k);
            printf("%d\n",x);

        }

    }
    return 0;
}