#include <fstream>
#include <cstdio>
#define NMAX 100001
using namespace std;
ofstream fout("aib.out");
struct arbore{int inc,sf,val;} arb[NMAX*3];
int n,m;
void adaug(int val,int poz)
{
    int tata=1,inc=1,sf=n;
    while(inc!=sf)
    {
        arb[tata].val+=val;
        if(poz<=(inc+sf)/2) tata=tata*2,sf=(inc+sf)/2;
        else tata=tata*2+1,inc=(inc+sf)/2+1;
    }
    arb[tata].val+=val;
}
int suma(int nod,int inc,int sf)
{
    int mij=(arb[nod].inc+arb[nod].sf)/2;
    if(inc==arb[nod].inc && sf==arb[nod].sf) return arb[nod].val;

    if(inc<=mij)
        if(sf>mij)
            return suma(nod*2,inc,mij)+suma(nod*2+1,mij+1,sf);
        else
            return suma(nod*2,inc,sf);
    else
        return suma(nod*2+1,inc,sf);
}
void numerotez(int nod,int inc,int sf)
{
    arb[nod].inc=inc; arb[nod].sf=sf;
    if(inc==sf) return;

    numerotez(nod*2,inc,(inc+sf)/2);
    numerotez(nod*2+1,(inc+sf)/2+1,sf);
}
int pozitie(int a)
{
    int nod=1;
    while(arb[nod].inc!=arb[nod].sf)
    {
        if(arb[nod].val==a) return arb[nod].sf;
        nod=nod*2;
    }
    if(arb[nod].val==a) return arb[nod].sf;
    return -1;
}
int main()
{
    freopen("aib.in","r",stdin);
    scanf("%d%d",&n,&m);
    numerotez(1,1,n);
    int x;
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&x);
        adaug(x,i);
    }
    int task,a,b;
    for(int i=1;i<=m;i++)
    {
        scanf("%d%d",&task,&a);
        if(task==0) {scanf("%d",&b); adaug(b,a);}
        else
            if(task==1)
                {scanf("%d",&b); fout<<suma(1,a,b)<<'\n';}
            else
                fout<<pozitie(a)<<'\n';
    }
    return 0;
}