#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;
long long s,a;
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 nod)
{
    if(s+arb[nod].val==a) {s=s+arb[nod].val; return arb[nod].sf;}

    if(s+arb[nod].val>a)
    {
        int k=pozitie(nod*2);
        if(s==a) return k;
        if(s<a)
        {
            k=pozitie(nod*2+1);
            if(s==a) return k;
        }
    }
    else
    {
        s=s+arb[nod].val;
        return -1;
    }
    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,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
            {
                s=0;
                fout<<pozitie(1)<<'\n';
            }
    }
    return 0;
}