#include <iostream>
#include <fstream>

using namespace std;

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

#define ultb(x) (x&(-x))

void update(int p[],int poz,int lun,int nract)
{
   for (int i =poz;i<=lun;i+=ultb(i))
   {
      p[i]+=nract;
   }
}

int sum1(int aib[],int poz)
{
   int s=0;
   for (int i =poz;i>0;i-=ultb(i))
   {
      s+=aib[i];
   }
   return s;
}

int sum2(int aib[],int pma,int pmi)
{
   int s=0;
   s=sum1(aib, pma)-sum1(aib, pmi-1);
   return s;
}

int sum3(int aib[], int sum, int lun)
{
   int s=0;
   int l=1;
   int r=lun;
   int mid=(r+l)/2;
   while (r>-l)
   {
      mid=(r+l)/2;
      if (sum1(aib,mid)>sum)
      {
         r=mid-1;
      }
      else if (sum1(aib,mid)<sum)
      {
         l=mid+1;
      }
      else if (sum1(aib,mid)==sum)
      {
         return mid;
      }
   }
}

int main()
{
    int lun, cr;
    in>>lun>>cr;
    int aib[lun];
    for (int i=1;i<=lun;i++)
    {
       aib[i]=0;
    }
      int nract=0;
      for (int i =1;i<=lun;i++)
      {
         in>>nract;
         update(aib,i,lun,nract);
      }
      int poz,a,b,val;
   int cer=-1;
   while (cr--)
   {
         in>>cer;
         if (cer==1)
         {
            in>>a>>b;
            out << sum2(aib,b,a)<<"\n";
         }
         if (cer==2)
         {
            in >> a;
            out << sum3(aib,a,lun) << "\n";
         }
         if (cer==0)
         {
            in>>poz>>val;
            update(aib,poz,lun,val);
         }
   }
}