#include <bits/stdc++.h>

const int MAX_N = 100005;

int n, m;

std::vector <int> bit(MAX_N);

int lsb(int value) {
  return (value & (- value));
}

void update(int pos, int value) {
  int p = pos;
  while (p <= n) {
    bit[p] += value;
    p += lsb(p);
  }
}

int query(int pos) {
  int p = pos, ans = 0;
  while (p > 0) {
    ans += bit[p];
    p -= lsb(p);
  }
  return ans;
}

int binary_query(int value, int steps) {
  int step = (1 << (31 - steps));
  int ans = 0;
  while (step > 0 && value > 0) {
    if ((ans + step) <= n && query(ans + step) <= value) {
      ans += step;
      value -= query(ans);
    }
    step >>= 1;
  }
  if (value == 0 && ans > 0) {
    return ans;
  } else {
    return - 1;
  }
}

int main() {
  int value, pos, lo, ri, op_type, steps;
  freopen("aib.in", "r", stdin);
  freopen("aib.out", "w", stdout);
  scanf("%d %d", &n, &m);
  steps = __builtin_clz(n);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &value);
    update(i, value);
  }
  while (m --) {
    scanf("%d", &op_type);
    if (op_type == 0) {
      scanf("%d %d", &pos, &value);
      update(pos, value);
    } else if (op_type == 1) {
      scanf("%d %d", &lo, &ri);
      printf("%d\n", query(ri) - query(lo - 1));
    } else if (op_type == 2) {
      scanf("%d", &value);
      printf("%d\n", binary_query(value, steps));
    }
  }
  return 0;
}