#include <stdio.h>
#include <stdlib.h>

#define N_MAX 100000

int aib[N_MAX + 1];
int aibSize;

int suma(int x) {
  int s = 0;
  while (x) {
    s += aib[x];
    x &= (x - 1);
  }
  return s;
}

void adauga(int val, int x) {
  do {
    aib[x] += val;
    x += x & (-x);
  } while (x <= aibSize);
}

int cauta(int val) {
  int start = 0, end = aibSize;
  while (start < end) {
    int mid = (start + end) / 2;
    if (suma(mid) > val)
      end = mid;
    else if (suma(mid) < val)
      start = mid + 1;
    else {
      start = mid;
      end = mid;
    }
  }

  while (suma(start-1) == val)
    start--;

  return start;
}

int main()
{
  FILE *in  = fopen("aib.in", "r");
  FILE *out = fopen("aib.out", "w");

  int n, m;
  fscanf(in, "%d %d", &n, &m);
  aibSize = n;

  int i, nr;
  for (i = 1; i <= n; i++) {
    fscanf(in, "%d", &nr);
    adauga(nr, i);
  }

  int j, operatie, a, b;
  for (j = 1; j <= m; j++) {
    fscanf(in, "%d", &operatie);
    switch (operatie) {
      case 0:
        fscanf(in, "%d %d", &a, &b);
        adauga(b,a);
        break;
      case 1:
        fscanf(in, "%d %d", &a, &b);
        fprintf(out, "%d\n", suma(b) - suma(a - 1));
        break;
      case 2:
        fscanf(in, "%d", &a);
        fprintf(out, "%d\n", cauta(a));
        break;
    }
  }

  fclose(in);
  fclose(out);

  return 0;
}