Juanzhang

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn = 5e4 + 10;
int n, m, q[maxn], q1[maxn], q2[maxn], ans[maxn];

struct Query {
  int op, l, r, k;
} Q[maxn];

struct BIT {
  int c[maxn]; ll sum[maxn];

  void add(int pos, int v) {
    int tmp = pos * v;
    for (; pos <= n; pos += pos & -pos) {
      c[pos] += v, sum[pos] += tmp;
    }
  }

  ll query(int pos) {
    ll tmp = pos + 1, res = 0;
    for (; pos; pos &= pos - 1) {
      res += c[pos] * tmp - sum[pos];
    }
    return res;
  }

  void upd(int l, int r, int v) {
    add(l, v), add(r + 1, -v);
  }

  ll query(int l, int r) {
    return query(r) - query(l - 1);
  }
} bit;

void divide(int l, int r, int ql, int qr) {
  if (l > r) return;
  if (ql == qr) {
    for (int i = l; i <= r; i++) {
      if (Q[q[i]].op == 2) ans[q[i]] = ql;
    }
    return;
  }
  int mid = (ql + qr) >> 1, p1 = 0, p2 = 0;
  for (int i = l; i <= r; i++) {
    Query &val = Q[q[i]];
    if (val.op == 1) {
      if (val.k <= mid) {
        q1[++p1] = q[i];
      } else {
        q2[++p2] = q[i], bit.upd(val.l, val.r, 1);
      }
    } else {
      ll s = bit.query(val.l, val.r);
      if (val.k <= s) {
        q2[++p2] = q[i];
      } else {
        q1[++p1] = q[i], val.k -= s;
      }
    }
  }
  for (int i = l; i <= r; i++) {
    Query val = Q[q[i]];
    if (val.op == 1 && val.k > mid) {
      bit.upd(val.l, val.r, -1);
    }
  }
  for (int i = 1; i <= p1; i++) {
    q[l + i - 1] = q1[i];
  }
  for (int i = 1; i <= p2; i++) {
    q[r - p2 + i] = q2[i];
  }
  divide(l, l + p1 - 1, ql, mid);
  divide(l + p1, r, mid + 1, qr);
}

int main() {
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= m; i++) {
    q[i] = i;
    scanf("%d %d %d %d", &Q[i].op, &Q[i].l, &Q[i].r, &Q[i].k);
  }
  divide(1, m, -n, n);
  for (int i = 1; i <= m; i++) {
    if (Q[i].op == 2) {
      printf("%d\n", ans[i]);
    }
  }
  return 0;
}