#include<cstdio>
using namespace std;
int n,m,t,a,b,v[100005];
inline int LSB(int x)
{
    return (x&(-x));
}
inline void update(int val, int poz)
{
    for (int i=poz;i<=n;i+=LSB(i))
        v[i]+=val;
}
inline int Sum(int poz)
{
    int sum=0;
    for (int i=poz;i;i-=LSB(i))
        sum+=v[i];
    return sum;
}
inline int cb(int x)
{
    int i=1,j=n,m,val;
    while (i<=j)
    {
        m=(i+j)>>1;
        val=Sum(m);
        if (val==x) return m;
        else
        {
            if (val<x) i=m+1;
            else j=m-1;
        }
    }
    return -1;
}
int main()
{
    int i;
    freopen("aib.in","r",stdin);
    freopen("aib.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (i=1;i<=n;++i)
    {
        scanf("%d",&t);
        update(t,i);
    }
    for (i=0;i<m;++i)
    {
        scanf("%d%d",&t,&a);
        if (t==2) printf("%d\n",cb(a));
        else
        {
            scanf("%d",&b);
            if (t) printf("%d\n",Sum(b)-Sum(a-1));
            else update(b,a);
        }
    }
    return 0;
}