← 返回题目列表

Codeforces · 555/B

B. 逃犯案

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

Android 安德鲁是一位银河系著名的侦探。他现在正在追捕隐藏在 Oxa-5 星球上的一名罪犯,该星球几乎完全被水覆盖。

唯一的旱地是由n个狭窄的岛屿连成一排组成的群岛。为了更方便,让我们将它们表示为直线上不相交的线段:岛 i 的坐标为 [li, ri],此外,对于 1 ≤ i ≤ n - 1,ri < li + 1。

为了实现目标,Andrewid 需要在每对相邻岛屿之间放置一座桥梁。如果 x 和 y 的坐标满足 li ≤ x ≤ ri、li + 1 ≤ y ≤ ri + 1 且 y - x = a,则可以在第 i 个岛和第 (i + 1) 个岛之间放置长度为 a 的桥。

为侦探提供了 m 个桥,每个桥最多可以使用一次。帮助他确定他得到的桥梁是否足以连接每对相邻的岛屿。

输入

第一行包含整数 n (2 ≤ n ≤ 2·105) 和 m (1 ≤ m ≤ 2·105) — 岛屿和桥梁的数量。

接下来的 n 行每行包含两个整数 li 和 ri (1 ≤ li ≤ ri ≤ 1018) — 岛端点的坐标。

最后一行包含 m 个整数 a1, a2, ..., am (1 ≤ ai ≤ 1018) — Andrewid 得到的桥的长度。

输出

如果不可能按照要求的方式在每对相邻岛屿之间放置一座桥,则在单行上打印“No”(不带引号),否则在第一行中打印“Yes”(不带引号),并在第二行中打印n - 1个数字b1,b2,...,bn - 1,这意味着在岛屿i和i + 1之间必须使用桥梁编号bi。

如果有多个正确答案,请打印其中任何一个。请注意,在此问题中,必须以正确的大小写打印“是”和“否”。

示例

输入 #1

4 4
1 4
7 8
9 10
12 14
4 5 3 8

输出 #1

Yes
2 3 1

输入 #2

2 2
11 14
17 18
2 9

输出 #2

No

输入 #3

2 1
1 1
1000000000000000000 1000000000000000000
999999999999999999

输出 #3

Yes
1

注意

例如,在第一个示例测试中,您可以将第二个电桥放置在点 3 和 8 之间,将第三个电桥放置在点 7 和 10 之间,并将第一个电桥放置在点 10 和 14 之间。

在第二个示例测试中,第一个桥太短,第二个桥太长,因此该解决方案不存在。