#include <fstream>
#define zero(x) ( (x ^ (x - 1)) & x )
using namespace std;
ifstream fin("aib.in");
ofstream fout("aib.out");
int i,j,k,n,q,r,aib[100001],a,b,x;
void sum(int loc,int val)
{
    int i;
    for (i=loc;i<=n;i+=zero(i))
    aib[i]+=val;
}
int query(int val)
{
    int i;
    int suma=0;
    for (i=val;i>0;i-=zero(i))
    suma+=aib[i];
    return suma;
}
int search(int val)
{
    int mij,st=1,dr=n;

    while (st<=dr)
    {
        mij=(st+dr)>>1;
        x=query(mij);
        if (x==val)
        {fout<<mij<<'\n';return 1;}
        else if (x<val)
        st=mij+1;
        else dr=mij-1;
    }
    return 0;
}
int search2(int val)
{
    int i,s;
    for (s=1;s<=n;s<<=1);

    for (i=0;s;s>>=1)
        if (i+s<=n)
            if (val>=aib[s])
            {
                val-=aib[s];i+=s;
                if (!val)
                    {fout<<i<<'\n';return 1;}
            }
    return 0;
}
int main()
{
    fin>>n>>q;
    for (i=1;i<=n;++i)
       {fin>>a;
        sum(i,a);}

    for (i=1;i<=q;++i)
    {
        fin>>r;
        if (!r)
        {
            fin>>a>>b;
            sum(a,b);
        }
        else if(r==1)
        {
            fin>>a>>b;
            fout<<(query(b)-query(a-1))<<'\n';
        }
        else if (r==2)
        {
            fin>>a;
            if (!search2(a))fout<<"-1\n";
        }
    }
    return 0;
}