#include <fstream>
#define zeros(x) (x&(x^(x-1)))
using namespace std;
#define LE 100666
ifstream f("aib.in");ofstream g("aib.out");
int n,m,x,i,j,b,h_sum,aa;
int tree[LE],typ;

void update(int pos,int value)
{
   for(;pos<=n;pos+=zeros(pos))
     tree[pos]+=value;
}
int  query(int pos)
{
  int result=0;

  for(;pos>0;pos-=zeros(pos))
    result+=tree[pos];
  return result;
}
int  max_find(int hmax)
{
    int step,pos=0,total=0;
    for(step=1;step<=n;step<<=1);

    for(;step;step>>=1)
      if(pos+step<=n&&total+tree[pos+step]<=hmax)
        {
            total+=tree[pos+step];
            pos+=step;
        }
    if (total!=hmax) return -1;
    return pos;
}
int main()
{
   f>>n>>m;
   for(i=1;i<=n;++i)
   {
       f>>aa;
       update(i,aa);
   }

   for(i=1;i<=m;++i)
   {
       f>>typ;
       if (typ==0)
       {
           f>>aa>>b;
           update(aa,b);
       }
       if (typ==1)
       {
           f>>aa>>b;
           g<<query(b)-query(aa-1)<<'\n';
       }
       if (typ==2)
       {
           f>>h_sum;
           g<<max_find(h_sum)<<'\n';
       }
   }

   f.close();g.close();
    return 0;
}