#include <cstdio>

const int MAX_N = 100000;

int N;
int aib[5 + MAX_N];

int terminal0(int x) {
  return x & -x;
}

void update(int poz, int val) {
  for (int i = poz; i <= N; i += terminal0(i)) {
    aib[i] += val;
  }
}

int query(int poz) {
  int s = 0;
  for (int i = poz; i >= 1; i -= terminal0(i)) {
    s += aib[i];
  }
  return s;
}

int main() {
  freopen("aib.in", "r", stdin);
  freopen("aib.out", "w", stdout);
  
  int M;
  scanf("%d%d", &N, &M);
  for (int i = 1; i <= N; i++) {
    int x;
    scanf("%d", &x);
    update(i, x);
  }
  for (int i = 1; i <= M; i++) {
    int type, a, b;
    scanf("%d%d", &type, &a);
    if (type == 0) {
      scanf("%d", &b);
      update(a, b);
    } else if (type == 1) {
      scanf("%d", &b);
      printf("%d\n", query(b) - query(a - 1));
    } else {
      int ans = -1;
      int st = 1;
      int dr = N;
      while (st <= dr) {
        int med = (st + dr) / 2;
        if (query(med) == a) {
          ans = med;
          break;
        } else if (query(med) < a) {
          st = med + 1;
        } else {
          dr = med - 1;
        }
      }
      printf("%d\n", ans);
    }
  }
  return 0;
}