C. Вилбур и точки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вилбур играет с множеством из n точек на координатной плоскости. Все точки имеют неотрицательные целочисленные координаты. Более того, если точка (x, y) принадлежит множеству Вилбура, то все точки (x', y'), такие, что 0 ≤ x' ≤ x и 0 ≤ y' ≤ y, также принадлежат этому множеству.

Теперь Вилбур хочет пронумеровать точки в имеющемся множестве, то есть присвоить им различные целочисленные номера от 1 до n. Чтобы нумерация была эстетически приятна, Вилбур хочет выполнить такое условие: если некоторая точка (x, y) получает номер i, тогда всем (x',y') из этого множества, таким, что 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) — размер множества точек, с которым играет Вилбур.

Далее следуют n строк с описаниями точек. В каждой строке записано два целых числа x и y (0 ≤ x, y ≤ 100 000), задающие одну точку из множества Вилбура. Гарантируется, что все точки различны. Также гарантируется, что если некоторая точка (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. Если существует несколько решений, выведите любое.

Примеры
Входные данные
5
2 0
0 0
1 0
1 1
0 1
0 -1 -2 1 0
Выходные данные
YES
0 0
1 0
2 0
0 1
1 1
Входные данные
3
1 0
0 0
2 0
0 1 2
Выходные данные
NO
Примечание

В первом примере точка (2, 0) получает номер 3, точка (0, 0) получает номер 1, точка (1, 0) получает номер 2, точка (1, 1) получает номер 5 и точка (0, 1) получает номер 4. Легко проверить, что такая нумерация является эстетически прятной, и yi - xi = wi.

Во втором примере специальные значения точек множества равны 0,  - 1 и  - 2, в то время как последовательность, которую Вилбуру даёт друг, равна 0, 1, 2. Следовательно, ответа не существует.