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

Drazil собирался подготовить следующую задачу про замощение прямоугольного поля n × m плитками размера 1 × 2:

"Дано прямоугольное поле, некоторые ячейки которого пустые, а некоторые ячейки — занятые. Требуется замостить все пустые ячейки плитками размера 1 × 2, таким образом, что никакие две плитки не накладываются друг на друга. Выведите какой-нибудь способ замощения."

Но потом Drazil понял, что он не хочет писать программу-чекер для проверки этой задачи. Его друг Varda посоветовал: "А что, если попросить участника выводить решение, только если оно существует и оно единственное? В противном случае участник должен вывести 'Not unique' ".

Размышляя над новой задачей Drazil подметил, что в новой постановке можно установить ограничения на размеры поля выше, чем для исходной задачи.

Сможете ли вы решить новую задачу?

Обратите внимание, что выводить 'Not unique' требуется как в случае, когда решение не единственное, так и в случае, когда решения вовсе не существует.

Входные данные

В первой строке следуют два целых числа n и m (1 ≤ n, m ≤ 2000).

В следующих n строках описывается поле. Символ '.' обозначает пустую ячейку, а символ '*' обозначает занятую ячейку.

Выходные данные

Если решения не существует, или же оно не уникальное, выведите строку "Not unique".

В противном случае требуется вывести вариант покрытия всех пустых ячеек плитками размера 1 × 2. Обозначайте горизонтальные плитки символами "<>", а вертикальные плитки — символами "^v". Для полного понимания формата вывода обратитесь к примерам вывода.

Примеры
Входные данные
3 3
...
.*.
...
Выходные данные
Not unique
Входные данные
4 4
..**
*...
*.**
....
Выходные данные
<>**
*^<>
*v**
<><>
Входные данные
2 4
*..*
....
Выходные данные
*<>*
<><>
Входные данные
1 1
.
Выходные данные
Not unique
Входные данные
1 1
*
Выходные данные
*
Примечание

В первом примере действительно существует два решения исходной задачи:


<>^
^*v
v<>

и


^<>
v*^
<>v

Таким образом, ответ — "Not unique".