#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,aux[1000];
int main()
{
    fin>>n>>m;
    for(i=1;i<=n;i++)
    {
        fin>>x;
        aux[i]=aux[i-1]+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";
            */
                a=1;
                b=n;

                do
                {
                    k=intunux ((a+b)/2);
                    if ( k<x )
                        a=(a+b)/2+1;
                    else
                        if (k>x)
                            b=(a+b)/2;
                }
                while (k!=x&&a<b);
                if (k==x)
                    fout<<(a+b)/2<<"\n";
                else
                    fout<<"-1\n";

            break;

        }

    }
    fin.close();
    fout.close();
    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;
    if (x>=1)
    {
        k=doila (x/2);
        if (x%2==0)
            return k*k;
        else
            return k*k*2;
    }
    else
        return 1;
}

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;
}