#P18869. [HONI 2017/2018 #1] Plahte

[HONI 2017/2018 #1] Plahte

题目描述

院子里铺着 NN 张矩形床单,边都平行于坐标轴。床单可以嵌套,但不同床单的边界既不相交也不接触。

有人发射了 MM 颗彩弹。每颗彩弹会把所有包含命中点的床单染上它的颜色,命中边界也算。床单会透过颜料,所以同一个点上的所有床单都会染色。不同彩弹的命中点互不相同,有些点可能落在所有床单之外。

对每张床单,求它一共染上了多少种不同的颜色。

输入格式

第一行两个整数 N,MN,M,满足 1≤N,M≤800001\le N,M\le80000。

接下来 NN 行,每行四个整数 Ai,Bi,Ci,DiA_i,B_i,C_i,D_i,分别表示第 ii 张床单左下角和右上角的坐标。

再接下来 MM 行,每行三个整数 Xj,Yj,KjX_j,Y_j,K_j,表示第 jj 颗彩弹的命中坐标和颜色编号。所有坐标和颜色编号均在 [1,109][1,10^9] 内。

输出格式

输出 NN 行,第 ii 行是第 ii 张床单上的不同颜色数。

样例

样例 1

输入

2 2
1 1 3 3
5 6 10 10
3 3 1
5 1 2

输出

1
0

样例 2

输入

3 3
1 1 7 7
2 2 6 6
3 3 5 5
4 4 1
2 6 2
4 7 3

输出

3
2
1

样例 3

输入

1 3
1 1 7 7
2 6 2
4 7 3
4 4 1

输出

3