/**
* author : Lăng Trọng Đạt
* created: 2025-08-16
**/
#include <bits/stdc++.h>
using namespace std;
#ifndef LANG_DAT
#define db(...) ;
#endif // LANG_DAT
#define int long long
#define mp make_pair
#define f first
#define se second
#define pb push_back
#define all(v) (v).begin(), (v).end()
using pii = pair<int, int>;
using vi = vector<int>;
#define FOR(i, a, b) for (int i = a; (i) <= (b); i++)
void mx(int& a, int b) { if (b > a) a = b; }
void mi(int& a, int b) { if (b < a) a = b; }
#define si(x) (int)(x.size())
const int INF = 1e9 + 5;
const int MOD = 1e9 + 7;
const int N = 1e6 + 5;
int g[N];
int n, m, k, a, b, c, d;
vector<int> nen = {-1}, nxt[N];
set<int> cover[N];
vector<vector<pii>> st;
struct Info {
int y1, y2, id, t;
} cur;
pii cha;
int cur_value;
void upd(int v = 1, int l = 1, int r = si(nen)) {
if (cur.y1 > r or l > cur.y2) return;
if (cur.id == 174)
db(v, st[v].back())
if (!st[v].empty() && st[v].back().f > cha.f) cha = st[v].back();
if (cur.y1 <= l && r <= cur.y2) {
st[v].push_back({cur.t, cur.id});
} else {
int mid = (l + r) / 2;
upd(2*v, l, mid); upd(2*v + 1, mid + 1, r);
}
}
void pop_st(int y1, int y2, int v = 1, int l = 1, int r = si(nen)) {
if (y1 > r or l > y2) return;
else if (y1 <= l && r <= y2) {
assert(st[v].back().se == cur_value);
st[v].pop_back();
} else {
int mid = (l + r) / 2;
pop_st(y1, y2, 2*v, l, mid); pop_st(y1, y2, 2*v + 1, mid + 1, r);
}
}
pii get(int y, int v = 1, int l = 1, int r = si(nen)) {
if (l > y or y > r) return {-1, -1};
if (l == r) {
return st[v].back();
} else {
int mid = (l + r) / 2;
return max({st[v].back(),
get(y, 2*v, l, mid),
get(y, 2*v + 1, mid + 1, r)});
}
}
int32_t main() {
cin.tie(0)->sync_with_stdio(0);
if (fopen("hi.inp", "r")) {
freopen("hi.inp", "r", stdin);
// freopen("./contest1_testdata/plahte/plahte.in.1a", "r", stdin);
freopen("hi.out", "w", stdout);
}
cin >> n >> m;
vector<array<int, 4>> events; // {x, type, y1, y2}
// type = -1: open rect, 0: point, INF: close rect
vector<pii> ord; // {dien tich, id}
FOR(i, 1, n) {
cin >> a >> b >> c >> d;
if (i == 3) db(a, b, c, d)
nen.pb(a); nen.pb(b); nen.pb(c); nen.pb(d);
events.push_back({a, -i, b, d}); // i just care about id when open it
events.push_back({c, INF + i, b, d});
ord.push_back({(c - a) * (d - b), i});
}
FOR(i, 1, m) {
cin >> a >> b >> k;
events.push_back({a, k, b, b});
nen.pb(a); nen.pb(b);
}
sort(all(nen));
nen.resize(unique(all(nen)) - nen.begin());
st = vector<vector<pii>>(5*si(nen), {{-1, -1}});
auto id = [&](int x) -> int {
return lower_bound(all(nen), x) - nen.begin();
};
// 174: (7435 716668642) (736777966 718695517)
// 3: (7416 716668623) (757243825 719274647)
// 1540: 7392 7238 757748639 722290487
// (nxt[3]) : ({ 3 174 581 1280 2274 2652 4412 4963 5261 6313
// 6448 6492 7113 7160 7237 7840 7978 8014 8361 8693
// 9670 10322 11191 11864 11913 12473 13102 13230 13778
// 14939 15162 15783 16277 16566 17122 17207 18441 19329 }
// )
db(id(107869543), id(764565751))
//
//
// db(nen)
sort(all(events));
int timer = 0;
for (auto[x, type, y1, y2] : events) {
// if (type == -3 or type == -1540 or type - INF == 3 or type - INF == 1540)
// db(x, type, y1, y2, "goc")
x = id(x); y1 = id(y1); y2 = id(y2);
// if (type == -3 or type == -1540 or type - INF == 3 or type - INF == 1540)
// db(type, x, y1, y2)
++timer;
if (type < 0) {
cur = {y1, y2, -type, timer}; cha = {-1, 0};
upd();
if (cha.f != -1) {
nxt[cha.se].push_back(-type);
}
if (-type == 174)
db(-type, cha)
} else if (type >= INF) {
cur_value = type - INF;
pop_st(y1, y2);
} else {
pii cha = get(y1);
if (cha.f != -1)
cover[cha.se].insert(type);
// db(cha)
}
}
sort(all(ord)); // làm theo các cạnh từ nhỏ -> lớn
vector<int> ans(n + 1);
for (auto[dien_tich, v] : ord) {
// db(v, nxt[v])
for (int u : nxt[v]) {
if (si(cover[u]) > si(cover[v])) swap(cover[u], cover[v]);
for (int c : cover[u]) cover[v].insert(c);
}
ans[v] = si(cover[v]);
}
FOR(i, 1, n) {
cout << ans[i] << "\n";
}
}
