#pragma GCC optimize("O3,inline")
#include <bits/stdc++.h>
using namespace std;
#define int long long
struct node {
int s, e, m, v, v1, v2, lazy;
node* l, * r;
node(int _s, int _e) : s(_s), e(_e), m((_s + _e) / 2), v(0), v1(-1), v2(s), lazy(0) {
if (s != e)
l = new node(s, m),
r = new node(m + 1, e);
}
void prop() {
if (s == e || lazy == 0) return;
l->v += lazy;
r->v += lazy;
l->lazy += lazy;
r->lazy += lazy;
l->v1 = r->v1 = v1;
lazy = 0;
}
void upd(int a, int b, int x, int i) {
if (b < s || a > e) return;
if (a <= s && b >= e) {
v += x;
lazy += x;
v1 = i;
return;
}
prop();
l->upd(a, b, x, i);
r->upd(a, b, x, i);
v = min(l->v, r->v);
if (v == l->v) v1 = l->v1, v2 = l->v2;
else v1 = r->v1, v2 = r->v2;
}
void upds(int n, int x) {
if (s == e) {
v += x;
return;
}
prop();
if (n <= m) l->upds(n, x);
else r->upds(n, x);
v = min(l->v, r->v);
if (v == l->v) v1 = l->v1, v2 = l->v2;
else v1 = r->v1, v2 = r->v2;
}
pair<int, pair<int, int>> qry(int a, int b) {
if (b < s || a > e) return { (int)1e15, {-1, -1} };
if (a <= s && b >= e) return { v, {v1, v2} };
prop();
auto lr = l->qry(a, b), rr = r->qry(a, b);
if (lr.first <= rr.first) return lr;
return rr;
}
} *root;
signed main() {
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int N, K, a, b, c, d; cin >> N >> K;
vector<pair<int, int>> v1, v2, v3, v4;
vector<int> ux, uy;
for (int i = 0; i < N; i++) {
cin >> a >> b >> c >> d;
if (a == 2 || a == 4) b--, c--;
if (a == 1) v1.push_back({ b, d });
else if (a == 2) v2.push_back({ b, d });
else if (a == 3) v3.push_back({ c, d });
else v4.push_back({ c, d });
if (a == 1 || a == 2) ux.push_back(b);
else uy.push_back(c);
}
sort(ux.begin(), ux.end());
ux.erase(unique(ux.begin(), ux.end()), ux.end());
sort(uy.begin(), uy.end());
uy.erase(unique(uy.begin(), uy.end()), uy.end());
for (auto& i : v1) i.first = lower_bound(ux.begin(), ux.end(), i.first) - ux.begin();
for (auto& i : v2) i.first = lower_bound(ux.begin(), ux.end(), i.first) - ux.begin();
for (auto& i : v3) i.first = lower_bound(uy.begin(), uy.end(), i.first) - uy.begin();
for (auto& i : v4) i.first = lower_bound(uy.begin(), uy.end(), i.first) - uy.begin();
priority_queue<int, vector<int>, greater<int>> pqfunny;
pqfunny.push(1e15);
root = new node(0, N);
int crntmax = 0, crntc = 0, minc = 1e15, prevloc = N, previdx = -1, eeeee = 1e15;
vector<priority_queue<int, vector<int>, greater<int>>> vpq1(N + 1, pqfunny);
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq1;
pq1.push({ 1e15, -1 });
stack<pair<int, int>> everysing1;
everysing1.push(pair<int, int>(N, 1e15));
for (auto& i : v2) vpq1[i.first].push(i.second); sort(v1.begin(), v1.end());
for (int i = v1.size() - 1; i >= 0; i--) {
if (minc > v1[i].second) {
everysing1.push({ i, v1[i].second });
root->upd(v1[i].first + 1, prevloc, minc, previdx);
minc = v1[i].second;
prevloc = v1[i].first;
previdx = i;
}
}
root->upd(0, prevloc, minc, previdx);
for (int i = 0; i <= N; i++) {
root->upds(i, vpq1[i].top());
vpq1[i].pop();
}
vector<int> res1 = { 0 };
while (1) {
auto res = root->qry(0, N);
if (res.first >= 1e15) break;
crntc += res.first;
res1.push_back(crntc);
if (res.second.first < crntmax) root->upd(0, v1[crntmax - 1].first, pq1.top().first - v1[res.second.first].second, pq1.top().second);
else {
for (int i = crntmax; i < res.second.first; i++) pq1.push({ v1[i].second, i });
if (crntmax) root->upd(0, v1[crntmax - 1].first, pq1.top().first - eeeee, pq1.top().second);
crntmax--;
while (res.second.first >= everysing1.top().first) {
if (crntmax == -1) root->upd(0, v1[everysing1.top().first].first, pq1.top().first - everysing1.top().second, everysing1.top().first);
else root->upd(v1[crntmax].first + 1, v1[everysing1.top().first].first, pq1.top().first - everysing1.top().second, everysing1.top().first);
everysing1.pop();
crntmax = everysing1.top().first;
}
crntmax++;
}
eeeee = pq1.top().first;
pq1.pop();
root->upds(res.second.second, vpq1[res.second.second].top());
vpq1[res.second.second].pop();
}
for (int i : res1) cout << i << '\n';
}
