I. Омкар и мозаика
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Омкар создает мозаику, используя цветные квадратные плитки, которые он размещает в сетке $$$n \times n$$$. Когда мозаика будет завершена, в каждой ячейке сетки будет либо глазурная, либо синоперная плитка. Однако в настоящее время он разместил плитки только в некоторых ячейках.

Завершенная мозаика будет шедевром тогда и только тогда, когда каждая плитка примыкает ровно к $$$2$$$ плиткам того же цвета ($$$2$$$ плитки являются примыкающими, если у них есть общая сторона.) Омкар хочет заполнить оставшиеся плитки так, чтобы мозаика стала шедевром. Теперь ему интересно, правда ли, что есть ровно один способ это сделать, и если да, то какой?

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

Первая строка содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 2000$$$).

Затем следуют $$$n$$$ строк с $$$n$$$ символами в каждой строке. $$$i$$$-й символ в $$$j$$$-й строке соответствует ячейке в строке $$$i$$$ и столбце $$$j$$$ сетки, и будет $$$S$$$, если Омкар поместил в эту ячейку синоперную плитку, $$$G$$$, если Омкар поместил глазурную плитку, и $$$.$$$, если она пуста.

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

В первой строке выведите UNIQUE, если существует уникальный способ получить шедевр, NONE, если Омкар не может его создать, и MULTIPLE, если существует более одного способа. Все буквы должны быть заглавными.

Если вы выведете UNIQUE, то после этого выведите $$$n$$$ дополнительных строк с $$$n$$$ символами в каждой строке, такими, что $$$i$$$-й символ в $$$j^{\text{th}}$$$ строке будет $$$S$$$, если плитка в строке $$$i$$$ и столбце $$$j$$$ шедевра — синоперная, и $$$G$$$, если она глазурная.

Примеры
Входные данные
4
S...
..G.
....
...S
Выходные данные
MULTIPLE
Входные данные
6
S.....
....G.
..S...
.....S
....G.
G.....
Выходные данные
NONE
Входные данные
10
.S....S...
..........
...SSS....
..........
..........
...GS.....
....G...G.
..........
......G...
..........
Выходные данные
UNIQUE
SSSSSSSSSS
SGGGGGGGGS
SGSSSSSSGS
SGSGGGGSGS
SGSGSSGSGS
SGSGSSGSGS
SGSGGGGSGS
SGSSSSSSGS
SGGGGGGGGS
SSSSSSSSSS
Входные данные
1
.
Выходные данные
NONE
Примечание

Для первого примера Омкар может получить шедевры

SSSS

SGGS

SGGS

SSSS

и

SSGG

SSGG

GGSS

GGSS.

Для второго примера можно доказать, что Омкар не может сложить плитки, чтобы создать шедевр.

Для третьего примера можно доказать, что данный шедевр — единственный шедевр, который Омкар может создать, сложив плитки.

Для четвертого примера очевидно, что единственная плитка в любой мозаике, которую создает Омкар, не может быть соседней с двумя плитками одного цвета, так как она будет соседней с $$$0$$$ плитками.