#include <iostream>
#include <fstream>
using namespace std;

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

int returnare_parinte(int x)
{
    int ct=0;

    while(x%2==0)
    {
        x=x/2;
        ct++;
    }

    x--;

    while(ct!=0)
    {
        x=x*2;
        ct--;
    }

    return x;

}

struct data {

int suma;

int frate_dr;
int ultim_copil;
int prim_copil;
int parinte;


}w[100005];

int v[100005];

int returnare_suma_pana_acm(int i)
{
    if(i==0)
        return 0;

    return w[i].suma+returnare_suma_pana_acm(w[i].ultim_copil);

}

void creare_arbore(int n)
{
    int fr_stang,parinte,i;

    for(i=1;i<=n;i++)
    {
        parinte=returnare_parinte(i);

        fr_stang=w[parinte].ultim_copil;

        w[i].suma=returnare_suma_pana_acm(fr_stang)+v[i];
        w[i].parinte=parinte;

        w[parinte].ultim_copil=i;

        if(fr_stang!=0)
            w[fr_stang].frate_dr=i;
        else
            w[parinte].prim_copil=i;


    }



}

void prima_operatie(int poz, int val_noua,bool parinte)
{
    if(poz==0)
        return;

    if(parinte==1)
        w[poz].suma=w[poz].suma+val_noua;


    if(w[poz].frate_dr!=0)
        prima_operatie(w[poz].frate_dr,val_noua,1);
    else
        prima_operatie(w[poz].parinte,val_noua,0);

}

int suma_pana_la_val(int i)
{
    if(i==0)
        return 0;

    return w[i].suma+suma_pana_la_val(w[i].parinte);

}

int operatia_doi(int a,int b)
{
    int x,y;

    x=suma_pana_la_val(a);
    y=suma_pana_la_val(b);

    return y-x+v[a];

}

int operatia_trei(int a,int i,int suma)
{
    if(i==0)
        return -1;


    if(suma==a)
        return i;

    if(suma>a)
        return -1;


    int fr_urmator=w[i].frate_dr;


    if(w[fr_urmator].suma<=a&&fr_urmator!=0)
    return  operatia_trei(a,fr_urmator,suma+w[fr_urmator].suma-w[i].suma);


    return operatia_trei(a,w[i].prim_copil,suma+w[w[i].prim_copil].suma);

}

int main()
{
    int n,m,i,a,b,c;

    fin>>n>>m;

    for(i=1;i<=n;i++)
        fin>>v[i];

    creare_arbore(n);

    for(i=1;i<=m;i++)
    {
        fin>>c;

        if(c==0)
        {
            fin>>a>>b;
            v[a]+=b;
            prima_operatie(a,b,1);
        }

        if(c==1)
        {
            fin>>a>>b;

            fout<<operatia_doi(a,b)<<"\n";
        }

        if(c==2)
        {
            fin>>a;

            fout<<operatia_trei(a,1,v[1])<<"\n";
        }

    }

    return 0;
}