#include <fstream>
#include <iostream>

using namespace std;

const int NMAX = 1e5;

int n;
int aib[1 + 2 * NMAX];

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

void update(int index, int value) {
  for (int i = index; i <= n; i += lsb(i)) {
    aib[i] += value;
  }
}

int query(int index) {
  int ans = 0;
  for (int i = index; i > 0; i -= lsb(i)) {
    ans += aib[i];
  }

  return ans;
}

int binary_search(int target) {
  int left = 1, right = n;
  while (left <= right) {
    int mid = (left + right) >> 1;

    int query_mid = query(mid);
    // printf("For mid = %d, query = %d\n", mid, query_mid);
    if (query_mid < target) {
      left = mid + 1;
    } else if (query_mid > target) {
      right = mid - 1;
    } else {
      return mid;
    }
  }

  return -1;
}

int main() {
  ifstream r("aib.in");
  ofstream w("aib.out");

  int m;
  r >> n >> m;

  for (int i = 1; i <= n; ++i) {
    int a;
    r >> a;

    update(i, a);
  }

  while (m--) {
    int type;
    r >> type;

    if (type == 0) {
      int index, value;
      r >> index >> value;

      update(index, value);
    } else if (type == 1) {
      int left, right;
      r >> left >> right;

      w << query(right) - query(left - 1) << '\n';
    } else {
      int value;
      r >> value;

      w << binary_search(value) << '\n';
    }
  }

  return 0;
}