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

int v[MAXN];
int x, y, n;

int lsb(int x){
  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 x){
  int st=1, dr=n, mij;
  while(st<=dr){
    mij=(dr+st)/2;
    if(x<=querry(mij))
      dr=mij;
    else
      st=mij;
  }
  if(querry(dr)==x)
    return dr;

  return -1;
}
int main(){
  FILE*fin=fopen("aib.in", "r");
  FILE*fout=fopen("aib.out", "w");
  int n, m, i, tip, x, y, nr, j;
  fscanf(fin, "%d%d", &n, &m);
  for(i=1; i<=n; i++){
    fscanf(fin, "%d", &nr);
    update(i, nr);
  }
//  for(i=1; i<=n; i++)
//    printf("%d ", v[i]);
  for(i=1; i<=m; i++){
    fscanf(fin, "%d", &tip);
    if(tip!=2){
      fscanf(fin, "%d%d", &x, &y);
      if(tip==0){
        update(x, y);
        fprintf(fout, "%d\n", v[x]);
      }
      if(tip==1)
        fprintf(fout, "%d\n", querry(y)-querry(x-1));
    }
    else{
      fscanf(fin, "%d", &x);
      fprintf(fout, "%d\n", cautbin(x));
    }
//    printf("%d %d\n", querry(2), querry(8));
//    for(j=1; j<=n; j++)
//      printf("%d ", v[j]);
//    printf("\n\n");
  }
  return 0;
}