#include <fstream>

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

void modificare ( int , int );
int doila ( int );
int nrdoi (int );
int intunux (int );
int v[100000],i,j,k,n,x,m,p,vl,a,b,s,gata;
int main()
{
    fin>>n>>m;
    for(i=1;i<=n;i++)
    {
        fin>>x;
        modificare(i,x);
    }
    for (i=1;i<=m;i++)
    {
        fin>>x;
        switch ( x )
        {
            case 0:
                fin>>p>>vl;
                modificare (p,vl);
            break;
            case 1:
                fin>>a>>b;
                if (a==1)
                    fout<<intunux(b)<<"\n";
                else
                    fout<<intunux(b)-intunux(a-1)<<"\n";
            break;
            case 2:
                fin>>x;
                gata=0;
                j=1;
                while (j<=n &&!gata)
                {
                    if(intunux(j)==x)
                        gata=1;
                    else
                        j++;
                }
                if (gata)
                    fout<<j<<"\n";
                else
                    fout<<"-1\n";
            break;

        }

    }
    return 0;
}


void modificare (int poz , int val )
{
    while (poz<=n)
    {
        v[poz]+=val;
        poz=poz+doila(nrdoi(poz));
    }
}

int nrdoi (int x)
{
    int j=0;
    while (!(x%2))
    {
        x=x/2;
        j++;
    }
    return j;
}

int doila ( int x )
{
    int i,k=1;
    for (i=0;i<x;i++)
        k=k*2;
    return k;
}

int intunux (int x )
{
    s=0;
    //fout<<"apelat pt "<<x;
    while (x>=1)
    {
        s+=v[x];
        x=x-doila(nrdoi(x));
    }
    //fout<<"afisat "<<s<<endl;
    return s;
}