#include <cstdio>



using namespace std;
int n;int v[100001];
int sum(int a)
{
    int s=0;
    while(a>=1)
    {
        s+=v[a];
        a=a-(a&(-a));
    }
    return s;
}
int sint(int a,int b)
{a--;
    int s=sum(b)-sum(a);
    return s;
}

void upd(int val,int poz)
{
    while(poz<=n)
    {
        v[poz]+=val;
        poz=poz+(poz&(-poz));
    }
}
int cauta(int st,int dr,int val)
{int m=(st+dr)/2;
    if(st==dr){if(sum(m)==val)return m;else return-1;}

if(val>sum(m))cauta(m+1,dr,val);
else if(val<sum(m))cauta(st,m,val);
else return m;
}

int main()
{freopen("aib.in","r",stdin);
freopen("aib.out","w",stdout);
int m,i,q,a,b;
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
{
    scanf("%d",&q);
    upd(q,i);
}
for(i=0;i<m;i++)
{
    scanf("%d",&q);
    if(q==0)
    {
        scanf("%d%d",&a,&b);
        upd(b,a);
    }
    else if(q==1)
    {
        scanf("%d%d",&a,&b);
        printf("%d\n",sint(a,b));
    }
    else
    {   scanf("%d",&q);
        printf("%d\n",cauta(1,n,q));
    }
}



    return 0;
}