Drazil собирался подготовить следующую задачу про замощение прямоугольного поля n × m плитками размера 1 × 2:
"Дано прямоугольное поле, некоторые ячейки которого пустые, а некоторые ячейки — занятые. Требуется замостить все пустые ячейки плитками размера 1 × 2, таким образом, что никакие две плитки не накладываются друг на друга. Выведите какой-нибудь способ замощения."
Но потом Drazil понял, что он не хочет писать программу-чекер для проверки этой задачи. Его друг Varda посоветовал: "А что, если попросить участника выводить решение, только если оно существует и оно единственное? В противном случае участник должен вывести 'Not unique' ".
Размышляя над новой задачей Drazil подметил, что в новой постановке можно установить ограничения на размеры поля выше, чем для исходной задачи.
Сможете ли вы решить новую задачу?
Обратите внимание, что выводить 'Not unique' требуется как в случае, когда решение не единственное, так и в случае, когда решения вовсе не существует.
Выходные данные
Если решения не существует, или же оно не уникальное, выведите строку "Not unique".
В противном случае требуется вывести вариант покрытия всех пустых ячеек плитками размера 1 × 2. Обозначайте горизонтальные плитки символами "<>", а вертикальные плитки — символами "^v". Для полного понимания формата вывода обратитесь к примерам вывода.
Примечание
В первом примере действительно существует два решения исходной задачи:
<>^
^*v
v<>
и
^<>
v*^
<>v
Таким образом, ответ — "Not unique".