Сбалансированная скобочная последовательность определяется как целая последовательность целых чисел, которая может быть построена по следующим правилам:
- Пустая последовательность сбалансирована.
- Если \([a_1,\ldots,a_n]\) и \([b_1,\ldots, b_m]\) сбалансированы, то их конкатенация \([a_1,\ldots,a_n,b_1,\ldots,b_m]\) сбалансирована.
- Если \(x\) — целое положительное число и \([a_1,\ldots,a_n]\) сбалансирована, то \([x,a_1,\ldots,a_n,-x]\) сбалансирована.
Положительные числа можно представить себе в виде открывающихся скобок, а отрицательные — в виде закрывающих скобок, где соответствующие скобки должны иметь одинаковый тип (абсолютное значение). Например, \([1, 2, -2, -1]\) и \([1, 3, -3, 2, -2, -1]\) сбалансированы, но \([1, 2, -1, -2]\) и \([-1, 1]\) не сбалансированы.
Есть \(2n\) карт. Каждая карта имеет число на лицевой стороне и число на оборотной. Каждое целое число \(1,-1,2,-2,\ldots,n,-n\) встречается на лицевой стороне ровно одной карты и на оборотной стороне ровной одной карты (необязательно той же карты).
Вы можете переупорядочить карты, как вам угодно. Вам не разрешено переворачивать карты, поэтому числа не могут перемещаться между лицевой и оборотной сторонами карты. Ваша задача — упорядочить карты так, чтобы последовательности, заданные числами на лицевых и оборотных сторонах, были сбалансированы, или сообщить, что это невозможно.
Выходные данные
В первой строке выведите «YES», если можно упорядочить карты, чтобы выполнялось условие. В противном случае выведите «NO». Вы можете выводить каждый символ в любом регистре.
Если это возможно, в следующих \(2n\) строках выведите карты в таком порядке, чтобы и лицевая и оборотная части были сбалансированы. Если есть несколько решений, то можно вывести любое.
Примечание
В первом примере лицевые числа образуют сбалансированную последовательность \([1,4,-4,-1,5,3,2,-2,-3,-5]\), а оборотные числа создают сбалансированную последовательность \([3,-3,4,-4,1,-1,2,5,-5,-2]\).
Во втором примере карты даются в таком порядке, что лицевые числа сбалансированы, а оборотные образуют несбалансированную последовательность \([1,2,-1,-2]\). Если бы мы поменяли местами вторую и третью карты, то сбалансировали бы оборотные числа и разбалансировали бы лицевые. Но нет такого порядка, который бы балансировал и то, и другое.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
1 3
-3 -5
4 -3
2 2
-1 -4
-2 5
3 -1
5 1
-4 4
-5 -2
|
YES
1 3
4 -3
-4 4
-1 -4
5 1
3 -1
2 2
-2 5
-3 -5
-5 -2
|
|
2
|
2
1 1
-1 2
2 -1
-2 -2
|
NO
|