Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official.
×

No tag edit access

C. Wilbur and Points

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputWilbur 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.

Input

The first line of the input consists of a single integer *n* (1 ≤ *n* ≤ 100 000) — 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* ≤ 100 000), 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} ( - 100 000 ≤ *w*_{i} ≤ 100 000) — the required special value of the point that gets number *i* in any aesthetically pleasing numbering.

Output

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.

Examples

Input

5

2 0

0 0

1 0

1 1

0 1

0 -1 -2 1 0

Output

YES

0 0

1 0

2 0

0 1

1 1

Input

3

1 0

0 0

2 0

0 1 2

Output

NO

Note

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.

Codeforces (c) Copyright 2010-2018 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Dec/15/2018 06:36:52 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|