#include <iostream>
#include <fstream>
#define nmax 100007
using namespace std;
ifstream fin("aib.in");
ofstream fout("aib.out");
long a[nmax];

int main()
{long n,k,x,y,poz,p,op,suma,sumb,j,i;
    fin>>n>>k;
    for(i=1;i<=n;i++)
    {fin>>x;
    poz=i;p=0;
     while(poz<=n)
      {a[poz]+=x;
          while(!((poz>>p) & 1))p++;
         poz+=(1<<p);
      }
    }


for(i=1;i<=k;i++)
{fin>>op;
if(op==0)
    {fin>>x>>y;
        poz=x;p=0;
    while(poz<=n)
        {a[poz]+=y;
        while(!((poz>>p) & 1))p++;
        poz+=(1<<p);
        p++;
        }

    }
    else if(op==1)
    {fin>>x>>y;
        suma=sumb=0;
        poz=y;p=0;
        while(poz>0)
        {sumb+=a[poz];
        while(!((poz>>p) & 1))p++;
        poz-=(1<<p);p++;
        }

        poz=x-1;p=0;
        while(poz>0)
        {suma+=a[poz];
        while(!((poz>>p) & 1))p++;
        poz-=(1<<p);p++;
        }
        fout<<sumb-suma<<'\n';
    }
    else {fin>>x;
          poz=0;p=1;
    while(x && p!=-1)
    {p=-1;
     while((1<<(p+1)<=n) && a[1<<(p+1)]<=x )p++;
     if(p>-1)
     {x-=a[1<<p];poz+=(1<<p);}
    }
    if(x==0 && poz!=0)
    fout<<poz<<'\n';
    else fout<<-1<<'\n';
    }

}


}