P4416 [COCI 2017/2018 #1] Plahte

小唐纳德决定有一天清洗他所有的 N 张白色床单。洗完后，他把它们放在后院的地上晾干。唐纳德放置床单的方式是**它们的边缘或角落都不接触，且没有边缘相交**，但可能会有小床单放在大床单上，或者一张床单完全覆盖另一张床单。做完这些后，唐纳德就去睡觉了。 唐纳德的朋友金姆不知怎么得知唐纳德正在晾床单，决定捉弄他。他从阁楼上找到了父亲的一个彩弹枪。和枪一起的，还有 M 颗不同颜色的彩弹球，但可能有多个球是相同颜色的。唐纳德一睡着，金姆就走进他的后院，开始用彩弹枪射击床单。我们都知道床单会渗色，所以当金姆射击最上面的床单时，那张床单会将彩弹的颜色渗透到下面所有的床单上。金姆用完所有的球后，开心地离开了唐纳德的后院。 当唐纳德醒来去收床单时，他大吃一惊。唐纳德的许多床单上都有一些新的颜色。由于唐纳德对准确的数据非常感兴趣，而他被惊吓得无法思考，他请求你告诉他每张床单上的新颜色数量。 我们可以将唐纳德的后院表示为一个无限的坐标系，床单表示为与坐标轴平行的矩形。金姆的射击可以表示为该坐标系中的点。 请注意：金姆的射击可能会错过所有床单，但每次射击的坐标是唯一的。

输入的第一行包含正整数 N（1 ≤ N ≤ 80 000），表示床单的数量，和 M（1 ≤ M ≤ 80 000），表示彩弹球的数量。 接下来的 N 行中的第 $i$ 行包含四个数字：第 $i$ 张床单的左下角坐标 $A_i$，$B_i$（1 ≤ $A_i$，$B_i$ ≤ $10^9$）和右上角坐标 $C_i$，$D_i$（1 ≤ $C_i$，$D_i$ ≤ $10^9$）。 接下来的 M 行中的第 $j$ 行包含金姆的第 $j$ 次射击落点的坐标 $X_j$，$Y_j$（1 ≤ $X_j$，$Y_j$ ≤ $10^9$），以及第 $j$ 颗球的颜色标记 $K_j$（1 ≤ $K_j$ ≤ $10^9$）。

输出的第 $i$ 行必须包含第 $i$ 张床单上的新颜色数量。

 题面翻译由 ChatGPT-4o 提供。