← 返回题目列表

Codeforces · 596/C

C. 威尔伯和点

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

Wilbur 正在玩坐标平面上的一组 n 点。所有点都有非负整数坐标。此外,如果某个点 (x, y) 属于该集合,则所有点 (x', y'),使得 0 ≤ x' ≤ x 且 0 ≤ y' ≤ y 也属于该集合。

现在 Wilbur 想要对他拥有的集合中的点进行编号,即为它们分配从 1 到 n 的不同整数。为了使编号美观,威尔伯施加了一个条件,如果某个点 (x, y) 得到编号 i,则集合中的所有 (x',y') 都必须被分配一个不小于 i 的编号,使得 x' ≥ x 和 y' ≥ y 必须被分配一个不小于 i 的编号。例如,对于一组四个点 (0, 0)、(0, 1)、(1, 0) 和 (1, 1),有两种美观的编号。一个是 1、2、3、4,另一个是 1、3、2、4。

威尔伯的朋友出现并挑战威尔伯。对于任何一点,他将其特殊值定义为 s(x, y) = y - x。现在他给威尔伯一些w1,w2,...,wn,并要求他在集合中找到一个美观的点编号,使得编号为i的点具有等于wi的特殊值,即s(xi,yi)= yi - xi = wi。

现在威尔伯要求你帮助他完成这项挑战。

输入

输入的第一行由一个整数 n (1 ≤ n ≤ 100 000) 组成 - Wilbur 正在玩的集合中的点数。

接下来的 n 行包含点描述。每行包含两个整数 x 和 y (0 ≤ x, y ≤ 100 000),它们给出 Wilbur 集合中的一个点。保证所有点都是不同的。此外,还保证如果输入中存在某个点 (x, y),则输入中也存在所有点 (x', y'),使得 0 ≤ x' ≤ x 和 0 ≤ y' ≤ y。

输入的最后一行包含 n 个整数。其中第 i 个是 wi ( - 100 000 ≤ wi ≤ 100 000) - 在任何美观的编号中获得编号 i 的点所需的特殊值。

输出

如果集合中存在美观的点编号,例如 s(xi, yi) = yi - xi = wi,则在输出的第一行打印“YES”。否则,打印“NO”。

如果存在解,则继续输出n行。在这些行的第 i 行上打印得到编号 i 的集合的点。如果有多个解决方案,请打印其中任何一个。

示例

输入 #1

5
2 0
0 0
1 0
1 1
0 1
0 -1 -2 1 0

输出 #1

YES
0 0
1 0
2 0
0 1
1 1

输入 #2

3
1 0
0 0
2 0
0 1 2

输出 #2

NO

注意

在第一个示例中,点 (2, 0) 获得数字 3,点 (0, 0) 获得数字 1,点 (1, 0) 获得数字 2,点 (1, 1) 获得数字 5,点 (0, 1) 获得数字 4。人们可以轻松检查此编号是否美观,并且 yi - xi = wi。

在第二个样本中,集合中点的特殊值为0、-1、-2,而朋友给Wilbur的序列是0、1、2。因此,答案不存在。