#include <fstream>

using namespace std;
ifstream f("aib.in");
ofstream g("aib.out");
int n,m,com,a,b;
int imp[100001],val[100001],sum[100001];
void adauga(int poz,int x)
{
    while(poz<=n)
    {
        sum[poz]+=x;
        poz+=1<<imp[poz];
    }
}
int sum2(int poz)
{
    int k=0;
    while(poz>=1)
    {
        k+=sum[poz];
        poz-=1<<imp[poz];
    }
    return k;
}
int cauta(int sm)
{
    int i=0,ad=1,capat=n;
    while(i<capat )
    {
        ad=1;
        while(i+ad<=n)
            if(sum[i+ad]>sm)
            {
                capat=i+ad;
                sm-=sum[i+(ad+1)/2];
                i+=(ad+1)/2;
                ad=n+1;
            }else if(sum[i+ad]==sm){
                    i=capat=i+ad;
                    ad=n+1;
                    sm=0;
            }
            else ad*=2;
    }
    if(!sm)
        g<<capat<<'\n';
    else g<<"-1\n";
}
int main()
{
    f>>n>>m;
    for(int i=2;i<=n;i*=2)
        for(int j=i;j<=n;j+=i)
            imp[j]++;
    for(int i=1;i<=n;i++)
        {
            f>>val[i];
            adauga(i,val[i]);
        }

    for(int i=1;i<=m;i++)
    {
        f>>com;
        if(com==0)
        {
            f>>a>>b;
            adauga(a,b);
            val[a]+=b;
        }else if(com==1)
        {
            f>>a>>b;
            g<<sum2(b)-sum2(a-1)<<'\n';
        }else{
            f>>a;
           cauta(a);
        }
    }
    return 0;
}