#include<stdio.h>
#include<assert.h>

#include<vector>
#include<algorithm>

using namespace std;

const int knmax = 100005;
int elements, tasks, aib[knmax];

inline int nbit(int x){
  return x &(-x);
}

void update(int pos, int val){
  if(pos > elements)
    return;

  aib[pos] += val;
  pos += nbit(pos);

  update(pos, val);
}

int query(int x){
  if(x == 0)
    return 0;
  return aib[x] + query(x - nbit(x));
}

void read(){
  assert(freopen("aib.in", "r", stdin) != NULL);

  scanf("%d%d", &elements, &tasks);

  int aux;
  for(int i = 1; i <= elements; ++i){
    scanf("%d", &aux);
    update(i, aux);
  }

}

int bs(int val){
  int left = 1, right = elements, mid, last = -1, aux;

  while(left <= right){
    mid = left + ((right - left) >> 1);

    aux = query(mid);

    if(aux == val)
      last = mid;

    if(aux >= val)
      right = mid - 1;
    else
      left = mid + 1;
  }

  return last;
}

void write(){
  assert(freopen("aib.out", "w", stdout) != NULL);

  int qry, aux_x, aux_y;
  for(int i = 1; i <= tasks; ++i){
    scanf("%d", &qry);

    if(qry == 0){
      scanf("%d%d", &aux_x, &aux_y);

      update(aux_x, aux_y);
    }
    else if(qry == 1){
      scanf("%d%d", &aux_x, &aux_y);

      printf("%d\n", query(aux_y) - query(aux_x - 1));
    }
    else{
      scanf("%d", &aux_x);

      printf("%d\n", bs(aux_x));
    }

  }

}

int main(){
  read();
  write();
  return 0;
}