Вилбур играет с множеством из 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.
Теперь Вилбур очень просит вас помочь ему с этой задачей.
Выходные данные
Если существует эстетически приятная нумерация точек множества, такая, что s(xi, yi) = yi - xi = wi, то выведите "YES" в первой строке выходных данных. В противном случае выведите "NO".
Если решение существует, далее выведите n строк. В i-й из них строк выведите точку множества, которая получит номер i. Если существует несколько решений, выведите любое.
Примечание
В первом примере точка (2, 0) получает номер 3, точка (0, 0) получает номер 1, точка (1, 0) получает номер 2, точка (1, 1) получает номер 5 и точка (0, 1) получает номер 4. Легко проверить, что такая нумерация является эстетически прятной, и yi - xi = wi.
Во втором примере специальные значения точек множества равны 0, - 1 и - 2, в то время как последовательность, которую Вилбуру даёт друг, равна 0, 1, 2. Следовательно, ответа не существует.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
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
|
|
2
|
3
1 0
0 0
2 0
0 1 2
|
NO
|