#include <fstream>
using namespace std;
ifstream fin ("aib.in");
ofstream fout ("aib.out");
int s[100001];
int len (int x)
{
  return x-(x&(x-1));
}
int main ()
{
  int n,m,i,nr,pz,q,a,b,sum,k,p,rez;
  fin>>n>>m;
  for (i=1;i<=n;i++)
  {
    fin>>nr;
    pz=i;
    while (pz<=n)
    {
      s[pz]+=nr;
      pz+=len(pz);
    }
  }
  for (i=1;i<=m;i++)
  {
    fin>>q;
    if (q==0)
    {
      fin>>a>>b;
      pz=a;
      while (pz<=n)
      {
        s[pz]+=b;
        pz+=len(pz);
      }
    }
    else
      if (q==1)
      {
        fin>>a>>b;
        pz=b;
        sum=0;
        while (pz>0)
        {
          sum+=s[pz];
          pz-=len(pz);
        }
        pz=a-1;
        while (pz>0)
        {
          sum-=s[pz];
          pz-=len(pz);
        }
        fout<<sum<<'\n';
      }
      else
        if (q==2)
        {
          fin>>k;
          rez=0;
          p=1;
          while (p*2<=n)
            p*=2;
          while (p>0)
          {
            if (rez+p<=n)
            {
              pz=rez+p;
              sum=0;
              while (pz>0)
              {
                sum+=s[pz];
                pz-=len(pz);
              }
              if (sum<=k)
                rez+=p;
              if (sum==k)
                p=0;
            }
            p/=2;
          }
          fout<<rez<<'\n';
        }
  }
  return 0;
}