#include <cstdio>
#define ub(x) (x&(-x))
using namespace std;
int i,j,n,m,instr,a[100010],x,y;
inline void updt(int x,int i)
{
    int k=0;
    for (k=i;k<=n;k+=ub(k))
        a[k]+=x;
    return ;
}
inline int s (int poz)
{
    int i,sum=0;
    for (i=poz;i>=1;i-=ub(i))
     sum+=a[i];
     return sum;
}
inline int caut(int val)
{
    int st,dr,mij;
    st=1;
    dr=n;
    while (st<=dr)
    {
        mij=(st+dr)/2;
        if (val==s(mij))return mij;
        else if (s(mij)>val)dr=mij-1;
        else if (s(mij)<val)st=mij+1;
    }
    return -1;
}
int main()
{
    freopen("aib.in","r",stdin);
    freopen("aib.out","w",stdout);
    scanf("%d %d\n",&n,&m);
    for (i=1;i<=n;i++)
    {
        scanf("%d ",&x);
        updt(x,i);
    }
    for (i=1;i<=m;i++)
    {
        scanf("%d\n",&instr);
        if (instr==0)
        {
            scanf("%d %d",&x,&y);
            updt(y,x);
        }
        else if (instr==1)
        {
            scanf("%d %d",&x,&y);
            printf("%d\n",s(y)-s(x-1));
        }
        else if (instr==2)
        {
            scanf("%d\n",&x);
            printf("%d\n",caut(x));
        }
    }
    return 0;
}