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 ₁, w ₂,…, 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.

Solution:

#include <bits/stdc++.h>

using namespace std;

const int N = 200010;

int main() {
int n;
scanf("%d", &n);
map < int, set < pair <int, int> > > mp;
for (int i = 0; i < n; i++) {
    int x, y;
    scanf("%d %d", &x, &y);
    mp[y - x].insert(make_pair(x, y));
  }
  vector < pair <int, int> > p(n);
for (int i = 0; i < n; i++) {
    int diff;
    scanf("%d", &diff);
    if (mp.empty()) {
      puts("NO");
      return 0;
    }
    p[i] = *(mp.begin());
    mp.erase(mp.begin());
  }
  vector <int> row(N, -1);
vector <int> col(N, -1);
for (int i = 0; i < n; i++) {
    int x = p[i].first;
    int y = p[i].second;
    if (row[x] != y - 1 || col[y] != x - 1) {
      puts("NO");
      return 0;
    }
    row[x]++;
    col[y]++;
  }
  puts("YES");
  for (int i = 0; i < n; i++) {
    int x = p[i].first;
    int y = p[i].second;
    printf("%d %d\n", x, y);
  }
  return 0;
}