#include <fstream>

using namespace std;

ifstream in ("aib.in");
ofstream out ("aib.out");

const int NMax=100005;
int aib[NMax],n,m;

void Actualizare_AIB(int arg, int pos)
{
    for (int i=pos;i<=n;i+=i&(-i))
    {
        aib[i]+=arg;
    }
}
int Suma (int arg)
{
    int ret=0;
    for (int i=arg;i>0;i-=i&(-i))
    {
        ret+=aib[i];
    }
    return ret;
}
void Read_And_Solve_Step1()
{
    in>>n>>m;
    for (int i=1;i<=n;i++)
    {
        int aux;
        in>>aux;
        Actualizare_AIB(aux,i);
    }
}
void Solve_Step_2_And_Print()
{
    int option,v1,v2;
    while(m--)
    {
        in>>option;
        if(!option)
        {
            in>>v1>>v2;
            Actualizare_AIB(v1,v2);
        }
        else if (option^2)
        {
            in>>v1>>v2;
            out<<Suma(v2)-Suma(v1-1)<<'\n';
        }
        else if (option^1)//BIN SRC
        {
            in>>v1;
            int st=1,dr=n,sw=0;
            while(st<=dr)
            {
                int mij=(st+dr);
                mij/=2;
                int sum;
                sum=Suma(mij);
                if(!(sum^v1))
                {
                    out<<mij<<'\n';
                    st=dr+1;
                    sw=0;
                }
                if(sum<v1)
                {
                    st=mij+1;
                }
                if(sum>v1)
                {
                    dr=mij-1;
                }
            }
            if(!(sw^0))
            {
                out<<-1<<'\n';
            }
        }
    }
}
int main()
{
    Read_And_Solve_Step1();
    Solve_Step_2_And_Print();
    return 0;
}