#include <stdio.h>
#include <stdlib.h>
#define MAXN 150004

int v[MAXN];
int x, y, n;
int lsb(int x){//lowest significant bit
  return x^(x&(x-1));
}
void update(int x, int y){
  while(x<=n){
    v[x]+=y;
    x+=lsb(x);
  }
}
inline int querry(int x){
  int s;
  s=0;
  while(x>0){
    s+=v[x];
    x-=lsb(x);
  }
  return s;
}

int cautbin(int st, int dr, int h){
  int mij, sol, aux;
  sol=-1;
  while(st<=dr){
//    printf("%d\n", mij);
    mij=(dr+st)/2;
    aux=querry(mij);
    if(h<=aux){
      dr=mij-1;
      if(aux==h)
        sol=mij;
    }
    else
      st=mij+1;
  }
  return sol;
}

int main(){
  FILE*fin=fopen("aib.in", "r");
  FILE*fout=fopen("aib.out", "w");
  int m, tip, p, i, nr;
  fscanf(fin, "%d%d", &n, &m);
  for(i=1; i<=n; i++){
    fscanf(fin, "%d", &nr);
    update(i, nr);
  }

  for(i=1; i<=m; i++){
    fscanf(fin, "%d", &tip);
    if(tip==0){
      fscanf(fin, "%d%d", &x, &y);
      update(x, y);
    }
    if(tip==1){
      fscanf(fin, "%d%d", &x, &y);
      fprintf(fout, "%d\n", querry(y)-querry(x-1));
    }
    if(tip==2){
      fscanf(fin, "%d", &x);
      fprintf(fout, "%d\n", cautbin(1, n, x));
    }
  }
  return 0;
}