一天，小唐纳德（Donald）决定洗干净他的 $N$ 张白色床单。洗完后，他把它们铺在后院的地上晾干。唐纳德放置床单时，使得任意两张床单的顶点或边界都不接触，且它们的边界也不相交。但是，他可能会把较小的床单放在较大的床单上面，或者一张床单完全覆盖另一张床单。做好这些后，唐纳德就去睡觉了。

唐纳德的朋友小金（Kim）不知怎么得知了唐纳德在晾床单的消息，决定捉弄他一下。他在阁楼里找到了父亲的一把彩弹枪。除了枪之外，还有 $M$ 颗不同颜色的彩弹，但也有可能有几颗彩弹颜色相同。唐纳德一睡着，小金就溜进他的后院，开始用彩弹枪射击床单。我们都知道床单是会“渗色”的，因此当小金射中处于最上层的床单时，该彩弹的颜色会向下渗透到其下方的所有床单上。小金用完所有的彩弹后，便高兴地离开了唐纳德的后院。

当唐纳德醒来去收床单时，他大吃一惊。在唐纳德的大多数床单上，都出现了若干种新颜色。由于唐纳德对准确的数据非常感兴趣，而他现在处于震惊之中无法思考，因此他请求你告诉他每张床单上新颜色的数量。

我们可以将唐纳德的后院表示为一个无限的直角坐标系，将床单表示为边平行于坐标轴的矩形。小金的射击可以表示为该坐标系中的点。

请注意：小金的射击有可能没有击中任何床单，但每次射击的坐标都是唯一的。

输入格式

输入的第一行包含两个正整数 $N$（$1 \le N \le 80\,000$），表示床单的数量，以及 $M$（$1 \le M \le 80\,000$），表示彩弹的数量。

接下来的 $N$ 行中，第 $i$ 行包含四个整数：第 $i$ 张床单的左下角坐标 $A_i, B_i$（$1 \le A_i, B_i \le 10^9$）和右上角坐标 $C_i, D_i$（$1 \le C_i, D_i \le 10^9$）。

接下来的 $M$ 行中，第 $j$ 行包含三个整数：小金第 $j$ 次射击落点的坐标 $X_j, Y_j$（$1 \le X_j, Y_j \le 10^9$），以及第 $j$ 颗彩弹的颜色编号 $K_j$（$1 \le K_j \le 10^9$）。

输出格式

输出共 $N$ 行。第 $i$ 行应包含第 $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

说明

图中的数字表示该次射击的彩弹颜色。

第一个样例的示意图

第二个样例的示意图