#include <fstream>
using namespace std;

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

namespace AIB { // sigur e aib
  struct node {
    int ind, pri;
    int val,sum;
    node *l, *r;
  } *nil = new node {0,0,0,0,0,0};
  using ns = node*;
  struct pns {
    ns l,r;
  };
  ns updnode(ns node, ns x, int poz) {
    (poz==0? node->l : node->r) =x;
    //cout << node->ind << "<-" << poz << '*' << x->ind << '\n';
    node->sum=node->l->sum+node->r->sum+node->val;
    return node;
  }
  ns merge(ns l, ns r) {
    return l==nil? r : 
            r==nil? l :
              l->pri>r->pri? updnode(l,merge(l->r,r),1) : 
                updnode(r,merge(l,r->l),0); 
  }
  pns split(ns node, int val) {
    //if(node!=nil)
    //cout << node->l->ind <<' ' <<node->r->ind <<  "ok\n";
    pns temp;
    return node==nil? pns{nil,nil} : 
            node->ind<=val? (temp=split(node->r,val),temp.l=updnode(node,temp.l,1),temp) :
              (temp=split(node->l,val),temp.r=updnode(node,temp.r,0),temp);
  }
  ns root=nil;
  void update(int poz,int val) {
    pns temp[2];
    temp[0]=split(root,poz-1);
    temp[1]=split(temp[0].r,poz);
    if(temp[1].l==nil)
      temp[1].l=new node{poz,abs(rand()),val,val,nil,nil};
    else
      temp[1].l->val+=val, temp[1].l->sum+=val;
    root=merge(temp[0].l,merge(temp[1].l,temp[1].r));
    //cout << poz << ' '<< val << ' '<<root->sum << '\n';
    
  }
  int query(int poz) {
    pns temp[2];
    temp[0]=split(root,poz);
    int rez=temp[0].l->sum;
    root=merge(temp[0].l,temp[0].r);
    return rez;
  }
  int querysegm(int l, int r) {
    return query(r)-query(l-1);
  }
  int query2(int val) { // se putea si doar in log iterand pe nivele, dar n-am chef
    int poz=0,t,last=-1,temp;
    for(int step=16; step>=0; step--) {
      //cout << step << "\n";
      if((t=query(temp=poz+(1<<step)))<=val)
        last=t,poz=temp;
    }
    if(last==val)
      return poz;
    return -1;
  }
};

signed main() {
  int n,q;
  cin >> n >> q;
  for(int i=1,x; i<=n; i++) {
    cin >> x;
    AIB::update(i,x);
  }
  for(int i=0,t,x,y; i<q;i++) {
    cin >> t>> x;
    if(t==0) {
      cin >> y;
      AIB::update(x,y);
    }
    else if(t==1) {
      cin >> y;
      cout << AIB::querysegm(x,y) <<'\n';
    }
    else
      cout << min(n,AIB::query2(x)) <<'\n';
  }
}