1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120

#include <map>
#include <set>
#include <queue>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long LL;
typedef unsigned long long ULL;

const int INF = 1000000007;
const int maxn = 50005;

int getint() {
	int r = 0; bool b = true; char c = getchar();
	while ('0' > c || c > '9') {if (c == '-') b = false; c = getchar();}
	while ('0' <= c && c <= '9') {r = r * 10 + (c - '0'); c = getchar();}
	if (b) return r;
	return -r;
}

LL sum[maxn<<2], qans;
int ans[maxn], n, q, toq, tom, tag[maxn<<2];
struct data_t { bool ismod; int l, r, id; LL k; } mod[maxn], que[maxn], dst[maxn], qle[maxn], qri[maxn], mle[maxn], mri[maxn];
inline bool cmpid(data_t a, data_t b) { return a.id < b.id; }

inline void add(int now, int l, int r, int v) {
	tag[now] += v;
	sum[now] += LL(r - l + 1) * LL(v);
}
void change(int now, int l, int r, int ll, int rr, int v) {
	if (ll <= l && r <= rr) {add(now, l, r, v);return;}
	int mid = (l + r) >> 1;
	if (tag[now]) {
		add(now<<1, l, mid, tag[now]);
		add(now<<1|1, mid+1, r, tag[now]);
		tag[now] = 0;
	}
	if (ll <= mid) change(now<<1, l, mid, ll, rr, v);
	if (rr > mid) change(now<<1|1, mid+1, r, ll, rr, v);
	sum[now] = sum[now<<1] + sum[now<<1|1];
}
void query(int now, int l, int r, int ll, int rr) {
	if (ll <= l && r <= rr) {qans += sum[now];return;}
	int mid = (l + r) >> 1;
	if (tag[now]) {
		add(now<<1, l, mid, tag[now]);
		add(now<<1|1, mid+1, r, tag[now]);
		tag[now] = 0;
	}
	if (ll <= mid) query(now<<1, l, mid, ll, rr);
	if (rr > mid) query(now<<1|1, mid+1, r, ll, rr);
}
void solve(int L, int R, int ql, int qr, int ml, int mr) {
	if (ql > qr) return;
	if (L == R) {for (int i = ql; i <= qr; ++i) ans[que[i].id] = L;return;}
	int mid = (L + R) >> 1, tot = 0, mtol = 0, mtor = 0, qtol = 0, qtor = 0;
	tot = merge(mod+ml, mod+mr+1, que+ql, que+qr+1, dst, cmpid) - dst;
	for (int i = 0; i < tot; ++i) {
		if (dst[i].ismod) {
			if (dst[i].k > mid) {
				change(1, 1, n, dst[i].l, dst[i].r, 1);
				mri[mtor++] = dst[i];
			} else {
				mle[mtol++] = dst[i];
			}
		} else {
			qans = 0ll;
			query(1, 1, n, dst[i].l, dst[i].r);
			if (qans >= dst[i].k) qri[qtor++] = dst[i];
			else {
				dst[i].k -= qans;
				qle[qtol++] = dst[i];
			}
		}
	}
	int ptr = ql;
	for (int i = 0; i < qtol; ++i) que[ptr++] = qle[i];
	for (int i = 0; i < qtor; ++i) que[ptr++] = qri[i];
	ptr = ml;
	for (int i = 0; i < mtol; ++i) mod[ptr++] = mle[i];
	for (int i = 0; i < mtor; ++i) mod[ptr++] = mri[i];
	for (int i = 0; i < tot; ++i)
		if (dst[i].ismod && dst[i].k > mid)
				change(1, 1, n, dst[i].l, dst[i].r, -1);
	solve(L, mid, ql, ql+qtol-1, ml, ml+mtol-1);
	solve(mid+1, R, ql+qtol, qr, ml+mtol, mr);
}

int main() {
	n = getint(); q = getint();
	int t, x, y; LL z;
	for (int i = 1; i <= q; ++i) {
		ans[i] = INF;
		t = getint(); x = getint(); y = getint(); z = getint();
		if (t == 1) {
			++tom;
			mod[tom].ismod = true;
			mod[tom].l = x;
			mod[tom].r = y;
			mod[tom].id = i;
			mod[tom].k = z;
		} else {
			++toq;
			que[toq].ismod = false;
			que[toq].l = x;
			que[toq].r = y;
			que[toq].id = i;
			que[toq].k = z;
		}
	}
	solve(-50000,50000,1,toq,1,tom);
	for (int i = 1; i <= q; ++i)
		if (ans[i] != INF)
			printf("%d\n", ans[i]);
	return 0;
}