시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 1024 MB | 1 | 1 | 1 | 100.000% |
Пете на день рождения подарили новую головоломку. Головоломка представляет собой цилиндр, состоящий из $n$ круглых слоев, нанизанных на одну вертикальную ось. Каждый слой можно вращать независимо от других. Каждый слой разбит на $n$ квадратиков, каждый из которых может быть либо черным, либо белым. В устойчивом состоянии квадратики соседних слоев находятся в точности друг под другом.
Для задания конфигурации головоломки удобно рассмотреть ее развертку --- <<разрезать>> поверхность цилиндра вдоль вертикальной линии, проходящей по границам квадратиков, и обозначить черные клетки символом <<0>>, а белые --- символом <<1>>. Пусть, например, одна из возможных разверток головоломки, приведенной на рисунке, следующая (на рисунке видно только первые три столбца этой развертки):
000110 001110 101000 001000 011111 011110
Задача решающего головоломку состоит в том, чтобы, поворачивая слои, добиться того, чтобы все вертикальные столбцы были различны. Например, головоломка приведенная выше, не решена, поскольку два из ее столбцов (четвертый и пятый на приведенной развертке) одинаковы. Если же повернуть нижний слой влево на один квадратик, развертка головоломки примет следующий вид:
000110 001110 101000 001000 011111 111100
Теперь все столбцы различны и следовательно головоломка решена.
Для того, чтобы решать головоломку было интереснее, на ее раскраску наложено дополнительное условие: нельзя повернуть один из слоев головоломки меньше чем на полный оборот таким образом, что внешний вид головоломки останется тем же. Так, например, для $n = 6$ слой с раскраской <<010101>> не разрешается, поскольку при его повороте на 2 квадратика внешний вид головоломки не меняется.
По заданной развертке головоломки выясните, можно ли ее решить, и если да, то приведите пример развертки решенной головоломки.
Первая строка входного файла содержит число $n$ --- количество слоев в головоломке и количество квадратиков в одном слое ($1 \le n \le 200$). Следующие $n$ строк содержат по $n$ символов, каждый из которых равен 0 или 1 --- развертку головоломки.
Если решить головоломку можно, на первой строке выходного файла выведите слово <<Yes
>>. В этом случае следующие $n$ строк должны содержать произвольную развертку решенной головоломки.
Если решить головоломку нельзя, выведите <<No
>> на первой строке выходного файла.
6 000110 001110 101000 001000 011111 011110
Yes 000110 001110 101000 001000 011111 111100