← 返回题目列表

Codeforces · 496/E

E. 分发零件

中文机器翻译题面 查看原题

你是一部新音乐剧的助理导演。该剧由 n 个音乐部分组成,每个部分必须由一名演员表演。选角结束后,导演选择了m位可以参加该剧的演员。你的任务是将角色分配给演员。然而,也有一些限制。

首先,每个演员都有一定的音域,有一些部分是他唱不了的。形式上,每个演员有两个整数,ci 和 di (ci ≤ di)——演员可以唱的最低和最高音符的音高。每个声部还有两个整数 - aj 和 bj (aj ≤ bj) - 声部中存在的最低音符和最高音符的音高。第 i 个演员可以表演第 j 个部分当且仅当 ci ≤ aj ≤ bj ≤ di,即该部分的每个音符都在演员的音域内。

根据合约,第i个演员最多可以表演ki部分。此外,你可以不给某些演员任何角色(然后他们参加人群场景)。

还有两个小时就要排练了,作业要快点做!

输入

第一行包含一个整数 n — 剧中的部分数量 (1 ≤ n ≤ 105)。

接下来的 n 行每行包含两个空格分隔的整数 aj 和 bj — 第 j 部分的音符范围 (1 ≤ aj ≤ bj ≤ 109)。

下一行包含一个整数 m — 演员的数量 (1 ≤ m ≤ 105)。

接下来的 m 行每行包含三个空格分隔的整数 ci、di 和 ki - 第 i 个演员的范围和他可以表演的部分数量 (1 ≤ ci ≤ di ≤ 109, 1 ≤ ki ≤ 109)。

输出

如果有一个作业满足以上所有条件,请在第一行打印一个单词“YES”(不带引号)。

在下一行中打印 n 个空格分隔的整数。第 i 个整数应该是执行第 i 个部分的演员的编号。如果有多个正确的作业,请打印其中任何一个。

如果没有正确的分配,则打印一个单词“NO”(不带引号)。

示例

输入 #1

3
1 3
2 4
3 5
2
1 4 2
2 5 1

输出 #1

YES
1 1 2

输入 #2

3
1 3
2 4
3 5
2
1 3 2
2 5 1

输出 #2

NO