#include <stdio.h>

#define MAX_N 131072

int aib[MAX_N + 1], aibSize;

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

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

int find(int val) {
  int mid, hi, lo;
  
  lo = 1;
  hi = aibSize;
  while (lo < hi) {
    mid = (lo + hi) / 2;
    if (suma(mid) < val)
      lo = mid + 1;
    else
      hi = mid;
  }
  mid = (lo + hi) / 2;
  if (suma(mid) > val)
    --mid;
  if (suma(mid) != val)
    return -1;

  return mid;
}

int main() {
  FILE * in, * out;
  int ops, a, b, operation, i, val;

  in  = fopen("aib.in", "r");
  out = fopen("aib.out", "w");

  fscanf(in, "%d %d", &aibSize, &ops);
  for (i = 1; i <= aibSize; i++) {
    fscanf(in, "%d", &val);
    add(val, i);
  }

  for (i = 1; i <= ops; i++) {
    fscanf(in, "%d", &operation);
    switch (operation) {
      case 0:
        fscanf(in, "%d %d", &a, &b);
        add(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", find(a));
        break;
    }
  }
  fclose(in);
  fclose(out);

  return 0;
}