题目描述

一天，$\red{Little Donald}$想要洗干净他的$\red{n}$张被单。洗完所有被单之后，他把它们放在后院的平地上晒干。$\red{Donald}$很好的摆放了这些被单，使得这些被单两 两之间不会在端点或边上接触，并且两两之间的边不会相交，但是可能一张更小的被单会放在一张更大的被单上面，或者一张被单会完全覆盖另外一张被单。做完这些事之后，$\red{Donald}$就去睡觉了。

然而，$\red{Donald}$的朋友，$\red{Kim，}$知道了$\red{Donald}$正在晒被单并且决定恶搞$\red{Donald}$。他从他爸爸的阁楼找到了一把彩弹枪。在这把枪中有$\red{m}$颗 彩弹，可能会有许多种不同颜色的彩弹，同时也可能有许多彩弹是有同一种颜色的。

在$\red{Donald}$睡着之后，$\red{Kim}$就进到$\red{Donald}$家的后院并开始用彩弹枪向这些被单射击。每次一张被单被射击之后，这个彩弹的颜色就会染在这张被单以及所有在这张被单下面的被单上。在$\red{Kim}$用完所有的彩弹之后，他就会开心地离开$\red{Donald}$家的后院。

当$\red{Donald}$醒来并且到后院看到自己的被单的时候，他被震惊了。在$\red{Donald}$的大多数被单上面都有许多新的颜色。由于$\red{Donald}$对于正确的数据十分感兴趣 ，并且他被震惊到无法思考了，所以他想让你告诉他每张被单上面的颜色的数量。

$\red{Donald}$的后院可以用一个平面坐标系表示，被单的边都是平行于坐标轴的，$\red{Kim}$射击的位置可以看成在平面中的一个点。

注意：$\red{Kim}$的一次射击可能不会到任意一个被单上，射击的位置两两之间互不相同。

输入格式

第一行两个正整数$\red{n(1≤}$$\red{n≤}$$\red{80000)}$和$\red{m(1≤}$$\red{m≤}$$\red{80000)，}$分别表示被单的数量和彩弹的数量

接下来$\red{n}$行，这$\red{n}$行中的第$\red{i}$行用四个数字$\red{A[i],B[i],C[i],D[i](1≤}$$\red{A[i],B[i],C[i],D[i]≤}$$\red{1e9)}$描述一张被单，

表示这张被单的左下角在$\red{(A[i],B[i])，}$右上角在$\red{(C[i],D[i])}$

接下来$\red{m}$行，这$\red{m}$行中的第$\red{i}$行用三个数字$\red{X[i],Y[i],K[i](1≤}$$\red{X[i],Y[i],K[i]≤}$$\red{1e9)}$描述一次射击，表示这次射击的位置是在点$\red{(X[i],Y[i])，}$以及这次射出去的彩弹的颜色为$\red{K[i]}$

输出格式

输出共$\red{n}$行，第$\red{i}$行表示染在第$\red{i}$张被单上面的颜色种数。

样例

输入样例1

2 2

1 1 3 3

5 6 10 10

3 3 1

5 1 2

输出样例1

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

输出样例2

3 
2
1

输入样例3

1 3

1 1 7 7

2 6 2

4 7 3

4 4 1

输出样例3

3

提示

样例$\red{1}$解释 点上的数字表示这次射击的彩弹的颜色。

样例$\red{2}$解释

数据范围

对于$\red{100\%}$的数据

$\red{1≤}$$\red{n≤}$$\red{80000}$

$\red{1≤}$$\red{m≤}$$\red{80000}$