#include <cstdio>
#include <math.h>

typedef unsigned int ui;

const int NMAX = 100005;
using namespace std;

ui N, M;
ui array[NMAX], debug[NMAX];

void add(ui pos, ui x) {
  array[pos] += x;
  debug[pos] += x;

  ui aux = 1;
  while( !(aux & pos) )
    aux <<= 1;

  while( aux <= N ) {
    if (!(aux & pos)){
      pos |= aux;
      array[pos] += x;
    }
    pos ^= aux;
    aux <<= 1;
  }
}

ui getSum(ui pos, ui sum) {
  if( !pos )
    return sum;

  ui aux = 1;
  while(!(aux & pos))
    aux <<= 1;
  sum += array[pos];
  pos ^= aux;
  return getSum(pos, sum);
}

ui findSum(ui sum) {
  ui step = 1 << ((ui) (log(N) / log(2)));
  ui s = 0, i = 0;

  while( i <= N && step > 0) {
    while ( i + step > N )
      step >>= 1;
    if ( s + array[i + step] < sum ) {
      s += array[i + step];
      i += step;
    } else if ( s + array[i + step] > sum ) {
      step >>= 1;
    } else
      return i + step;
  }

  return -1;
}

void read() {
  freopen("aib.in", "r", stdin);
  freopen("aib.out", "w", stdout);
  scanf("%u%u", &N, &M);

  ui x;
  for(ui i = 1; i <= N; i++) {
    scanf("%u", &x);
    add(i, x);
  }
}

void solve() {
  ui t, a, b;
  for(ui i = 1; i <= M; i++) {
    scanf("%u", &t);
    switch(t) {
      case 0: scanf("%u %u", &a, &b);
              add(a, b);
              break;
      case 1: scanf("%u %u", &a, &b);
              printf("%u\n", getSum(b, 0) - getSum(a - 1, 0));
              break;
      case 2: scanf("%u", &a);
              printf("%i\n", findSum(a));
              break;
    }
  }
}

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