#include <cstdio>

const int MAXN = 1e5;

int aib[MAXN + 1];

void add(int x, int val, int n) {
  while (x <= n) {
    aib[x] += val;
    x += x & -x;
  }
}

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

int search(int a, int n) {
  int st = 1, dr = n, s, m;
  while (st <= dr) {
    m = (st + dr) / 2;
    s = sum(m);
    if (a <= s) {
      dr = m - 1;
    } else {
      st = m + 1;
    }
  }
  if (sum(st) == a) {
    return st;
  } else {
    return -1;
  }
}

int main() {
  int n, m, a, b, op;
  FILE *fin = fopen("aib.in", "r");
  fscanf(fin, "%d%d", &n, &m);
  for (int i = 1; i <= n; ++i) {
    fscanf(fin, "%d", &a);
    add(i, a, n);
  }
  FILE *fout = fopen("aib.out", "w");
  for (int i = 0; i < m; ++i) {
    fscanf(fin, "%d", &op);
    switch (op) {
      case 0: fscanf(fin, "%d%d", &a, &b);
              add(a, b, n);
              break;
      case 1: fscanf(fin, "%d%d", &a, &b);
              fprintf(fout, "%d\n", sum(b) - sum(a - 1));
              break;
      case 2: fscanf(fin, "%d", &a);
              fprintf(fout, "%d\n", search(a, n));
              break;
    }
  }
  fclose(fin);
  fclose(fout);
  return 0;
}