Задача I. Головоломка ≡
| Автор: | Восьмая всероссийская командная олимпиада школьников по программированию | Ограничение времени: | 2 сек | |
| Входной файл: | puzzle.in | Ограничение памяти: | 256 Мб | |
| Выходной файл: | puzzle.out |
Условие
Пете на день рождения подарили новую головоломку. Головоломка представляет собой цилиндр,
состоящий из n круглых слоев, нанизанных на одну вертикальную ось. Каждый слой можно вращать
независимо от других. Каждый слой разбит на n квадратиков, каждый из которых может быть либо
черным, либо белым. В устойчивом состоянии квадратики соседних слоев находятся в точности друг
под другом.
Для задания конфигурации головоломки удобно рассмотреть ее развертку — "разрезать" поверхность цилиндра вдоль вертикальной линии, проходящей по границам квадратиков, и обозначить черные клетки символом "0", а белые — символом "1". Пусть, например, одна из возможных разверток головоломки, приведенной на рисунке, следующая (на рисунке видно только первые три столбца этой развертки):
000110 001110 101000 001000 011111 011110
Задача решающего головоломку состоит в том, чтобы, поворачивая слои, добиться того, чтобы все вертикальные столбцы были различны. Например, головоломка приведенная выше, не решена, поскольку два из ее столбцов (четвертый и пятый на приведенной развертке) одинаковы. Если же повернуть нижний слой влево на один квадратик, развертка головоломки примет следующий вид:
000110 001110 101000 001000 011111 111100Теперь все столбцы различны и следовательно головоломка решена. Для того, чтобы решать головоломку было интереснее, на ее раскраску наложено дополнительное условие: нельзя повернуть один из слоев головоломки меньше чем на полный оборот таким образом, что внешний вид головоломки останется тем же. Так, например, для n = 6 слой с раскраской "010101" не разрешается, поскольку при его повороте на 2 квадратика внешний вид головоломки не меняется.
По заданной развертке головоломки выясните, можно ли ее решить, и если да, то приведите пример развертки решенной головоломки.
Формат входного файла
Первая строка входного файла содержит число n — количество слоев в головоломке и количество квадратиков в одном слое. Следующие n строк содержат по n символов, каждый из которых равен 0 или 1 — развертку головоломки.
Формат выходного файла
Если решить головоломку можно, на первой строке выходного файла выведите слово "Yes". В этом случае следующие n строк должны содержать произвольную развертку решенной головоломки.
Если решить головоломку нельзя, выведите "No" на первой строке выходного файла.
Ограничения
1 ≤ n ≤ 200
Примеры тестов
| № | Входной файл (puzzle.in) |
Выходной файл (puzzle.out) |
|---|---|---|
| 1 | |
|