#include <iostream>
using namespace std;

typedef long long llong;
const int nmax = 1e5 + 7;

static int n, m;
static int a[nmax];
static llong aib[nmax];

void solve() {

  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    aib[i] = a[i];
  }

  for (int i = 1; i <= n; i++) {
    if (i + (i & -i) <= n) aib[i + (i & -i)] += aib[i];
  }

  while (m--) {

    int c;
    cin >> c;
    
    if (c == 0) {
      int a, b;
      cin >> a >> b;
      for (; a <= n; a += a & -a) aib[a] += b;
      continue;
    }

    if (c == 1) {
      int a, b;
      cin >> a >> b;
      llong s = 0;
      for (int p = b; p; p -= p & -p) s += aib[p];
      for (int p = a - 1; p; p -= p & -p) s -= aib[p];
      cout << s << '\n';
      continue;
    }

    if (c == 2) {
      int a;
      cin >> a;
      if (a == 0) { cout << -1 << '\n'; continue; }
      int s = 0, r = 0;
      for (int p = 1 << 20; p; p >>= 1) {
        if (r + p <= n && s + aib[r + p] <= a) {
          s += aib[r + p];
          r += p;
        }
      }
      cout << r << '\n';
      continue;
    }
  }
  
}

int main() {

  #ifdef LOCAL
  freopen("file.in", "r", stdin);
  #else
  freopen("aib.in", "r", stdin);
  freopen("aib.out", "w", stdout);
  #endif

  ios_base::sync_with_stdio(false), cin.tie(NULL);

  solve();

}