Wilbur and Points

题目描述

Wilbur is playing with a set of $ n $ points on the coordinate plane. All points have non-negative integer coordinates. Moreover, if some point ( $ x $ , $ y $ ) belongs to the set, then all points ( $ x' $ , $ y' $ ), such that $ 0<=x'<=x $ and $ 0<=y'<=y $ also belong to this set. Now Wilbur wants to number the points in the set he has, that is assign them distinct integer numbers from $ 1 $ to $ n $ . In order to make the numbering aesthetically pleasing, Wilbur imposes the condition that if some point ( $ x $ , $ y $ ) gets number $ i $ , then all ( $ x' $ , $ y' $ ) from the set, such that $ x'>=x $ and $ y'>=y $ must be assigned a number not less than $ i $ . For example, for a set of four points ( $ 0 $ , $ 0 $ ), ( $ 0 $ , $ 1 $ ), ( $ 1 $ , $ 0 $ ) and ( $ 1 $ , $ 1 $ ), there are two aesthetically pleasing numberings. One is $ 1 $ , $ 2 $ , $ 3 $ , $ 4 $ and another one is $ 1 $ , $ 3 $ , $ 2 $ , $ 4 $ . Wilbur's friend comes along and challenges Wilbur. For any point he defines it's special value as $ s(x,y)=y-x $ . Now he gives Wilbur some $ w_{1} $ , $ w_{2} $ ,..., $ w_{n} $ , and asks him to find an aesthetically pleasing numbering of the points in the set, such that the point that gets number $ i $ has it's special value equal to $ w_{i} $ , that is $ s(x_{i},y_{i})=y_{i}-x_{i}=w_{i} $ . Now Wilbur asks you to help him with this challenge.

输入输出格式

输入格式

The first line of the input consists of a single integer $ n $ ( $ 1<=n<=100000 $ ) — the number of points in the set Wilbur is playing with. Next follow $ n $ lines with points descriptions. Each line contains two integers $ x $ and $ y $ ( $ 0<=x,y<=100000 $ ), that give one point in Wilbur's set. It's guaranteed that all points are distinct. Also, it is guaranteed that if some point ( $ x $ , $ y $ ) is present in the input, then all points ( $ x' $ , $ y' $ ), such that $ 0<=x'<=x $ and $ 0<=y'<=y $ , are also present in the input. The last line of the input contains $ n $ integers. The $ i $ -th of them is $ w_{i} $ ( $ -100000<=w_{i}<=100000 $ ) — the required special value of the point that gets number $ i $ in any aesthetically pleasing numbering.

输出格式

If there exists an aesthetically pleasant numbering of points in the set, such that $ s(x_{i},y_{i})=y_{i}-x_{i}=w_{i} $ , then print "YES" on the first line of the output. Otherwise, print "NO". If a solution exists, proceed output with $ n $ lines. On the $ i $ -th of these lines print the point of the set that gets number $ i $ . If there are multiple solutions, print any of them.

输入输出样例

输入样例 #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

说明

In the first sample, point ( $ 2 $ , $ 0 $ ) gets number $ 3 $ , point ( $ 0 $ , $ 0 $ ) gets number one, point ( $ 1 $ , $ 0 $ ) gets number $ 2 $ , point ( $ 1 $ , $ 1 $ ) gets number $ 5 $ and point ( $ 0 $ , $ 1 $ ) gets number $ 4 $ . One can easily check that this numbering is aesthetically pleasing and $ y_{i}-x_{i}=w_{i} $ . In the second sample, the special values of the points in the set are $ 0 $ , $ -1 $ , and $ -2 $ while the sequence that the friend gives to Wilbur is $ 0 $ , $ 1 $ , $ 2 $ . Therefore, the answer does not exist.