#include <bits/stdc++.h> #define fi first #define se second #define xn '\n' using namespace std ; typedef long long ll ; typedef pair <int, int> ii ; typedef pair <ll, int> li; const int Mod = 1e9 + 7 ; const int N = 1e5 ; const ll MAX = 1e18; int dy[] = { 0 , -1 , 0 , 1 } ; int dx[] = { -1 , 0 , 1 , 0 } ; struct hinh{ int x1, y1, x2, y2; }; struct diem{ int x, y, color; }; struct nen{ int val, hinh, loai, id; }; struct one{ int y1, y2, id; }; struct two{ int y, color; }; int n, m, comp_val; int par[N + 22], ans[N + 22], st[N * 6 * 4 + 22], lazy[N * 6 * 4 + 22]; hinh cn[N + 22]; diem d[N + 22]; nen p[N * 6 + 22]; vector <one> be[N * 6 + 22], en[N * 6 + 22]; vector <two> node[N * 6 + 22]; set <int> set_cn[N + 22], pos; vector <int> g[N + 22]; bool cmp_nen(nen x, nen y){ return x.val < y.val; } bool cmp_cn(hinh a, hinh b){ if (a.y1 == b.y1) return a.x1 > b.x1; return a.y1 > b.y1; } void compressed(){ int sz = 0; for (int i = 1; i <= n; i++){ p[++sz] = {cn[i].x1, 1, 1, i}; p[++sz] = {cn[i].y1, 1, 2, i}; p[++sz] = {cn[i].x2, 1, 3, i}; p[++sz] = {cn[i].y2, 1, 4, i}; } for (int i = 1; i <= m; i++){ p[++sz] = {d[i].x, 2, 1, i}; p[++sz] = {d[i].y, 2, 2, i}; } sort(p + 1, p + sz + 1, cmp_nen); p[0].val = - 1; for (int i = 1; i <= sz; i++){ if (p[i].val != p[i - 1].val) comp_val++; int tmp = p[i].hinh, dk = p[i].loai, id = p[i].id; if (tmp == 1){ if (dk == 1) cn[id].x1 = comp_val; if (dk == 2) cn[id].y1 = comp_val; if (dk == 3) cn[id].x2 = comp_val; if (dk == 4) cn[id].y2 = comp_val; } if (tmp == 2){ if (dk == 1) d[id].x = comp_val; if (dk == 2) d[id].y = comp_val; } } } void create(){ for (int i = 1; i <= n; i++){ be[cn[i].x1].push_back({cn[i].y1, cn[i].y2, i}); en[cn[i].x2].push_back({cn[i].y1, cn[i].y2, i}); } for (int i = 1; i <= m; i++){ node[d[i].x].push_back({d[i].y, d[i].color}); } } void down(int id){ int val = lazy[id]; if (val == - 1) return ; st[id * 2] = val; lazy[id * 2] = val; st[id * 2 + 1] = val; lazy[id * 2 + 1] = val; lazy[id] = - 1; } void update(int id, int l, int r, int u, int v, int val){ if (l > v || r < u) return ; if (u <= l && r <= v){ st[id] = val; lazy[id] = val; return ; } down(id); int mid = (l + r) >> 1; update(id * 2, l, mid, u, v, val); update(id * 2 + 1, mid + 1, r, u, v, val); st[id] = max(st[id * 2], st[id * 2 + 1]); } int get(int id, int l, int r, int u, int v){ if (l > v || r < u) return 0; if (u <= l && r <= v) return st[id]; down(id); int mid = (l + r) >> 1; return max(get(id * 2, l, mid, u, v), get(id * 2 + 1, mid + 1, r, u, v)); } void sweep_line(){ memset(lazy, - 1, sizeof(lazy)); for (int x = 1; x <= comp_val; x++){ for (one td : be[x]){ par[td.id] = get(1, 1, comp_val, td.y1, td.y2); update(1, 1, comp_val, td.y1, td.y2, td.id); } for (two td : node[x]){ int id = get(1, 1, comp_val, td.y, td.y); if (id != 0) set_cn[id].insert(td.color); } for (one td : en[x]){ update(1, 1, comp_val, td.y1, td.y2, par[td.id]); } } } void dfs(int u){ for (int v : g[u]){ dfs(v); if (u == 0) continue; if ( (int)set_cn[u].size() < (int) set_cn[v].size()) swap(set_cn[u], set_cn[v]); for (int x : set_cn[v]) set_cn[u].insert(x); set_cn[v].clear(); } ans[u] = (int) set_cn[u].size(); } void solution(){ for (int i = 1; i <= n; i++){ g[par[i]].push_back(i); } dfs(0); for (int i = 1; i <= n; i++){ cout << ans[i] << xn; } } int main() { ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); cin >> n >> m; for (int i = 1; i <= n; i++){ cin >> cn[i].x1 >> cn[i].y1 >> cn[i].x2 >> cn[i].y2; } for (int i = 1; i <= m; i++){ cin >> d[i].x >> d[i].y >> d[i].color; } compressed(); create(); sweep_line(); solution(); return 0 ; }