#include <stdio.h>
#include <bits/stdc++.h>

#define rep(i, n) for(int i = 0; i < (int)(n); i++)

using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

struct AIB {
  AIB(int _n) {
    n = _n;
    size = 1;
    while(size < n) size *= 2;
    aib.resize(size+1, 0);
  }
  void upd(int pos, int val) {
    for(int i = pos; i <= size; i += i&-i) {
      aib[i] += val;
    }
  }
  int sum(int x) { // sum over [1..l]
    int res = 0;
    for(int i = min(x, size); i > 0; i -= i&-i) {
      res += aib[i];
    }
    return res;
  }
  // void debug() {
  //   for(int i = 0; i <= size; i++) {
  //     cout << i << ":\t" << bitset<4>(i) << ":\t" << aib[i] << endl;
  //   }
  // }
  void debug_values() {
    for(int i = 1; i <= size; i++) {
      cout << value(i) << ' ';
    }
    cout << endl;
  }
  int value(int x) {
    int res = aib[x];
    for(int i = x-1, step = x & -x; i > x - step; i -= i&-i) {
      res -= aib[i];
    }
    return res;
  }
  int query(int val) {
    int i = 0;
    // this finds the largest position i such that sum[i] < val;
    for(int step = size; step; step /= 2) { // INV: aib[i] < val;
      if (i + step <= size) {
        if (aib[i+step] < val) {
          i += step;
          val -= aib[i];
        }
      }
    }
    i++;
    if (i > n || value(i) != val) return -1;
    return i;
  }
  int size, n;
  vi aib;
};

int main(void) {
  freopen("aib.in", "r", stdin);
  freopen("aib.out", "w", stdout);
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(NULL);
  int n, m;
  cin >> n >> m;
  AIB aib{n};
  rep(i, n) {
    int x;
    cin >> x;
    aib.upd(i+1, x);
  }
  // aib.debug_values();
  int op, pos, val, l, r;
  while(m--) {
    cin >> op;
    if (op == 0) {
      cin >> pos >> val;
      aib.upd(pos, val);
      // aib.debug();
      // aib.debug_values();
    } else if (op == 1) {
      cin >> l >> r;
      cout << aib.sum(r) - aib.sum(l-1) << "\n";
    } else {
      cin >> val;
      cout << aib.query(val) << "\n";
    }
  }
  return 0;
}