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

Игорь много занимался шахматами, и теперь ему надоела игра по обычным правилам. Он собирается придумать новые правила игры и обрести мировую славу.

Доска в шахматах Игоря имеет форму квадрата n × n клеток. Игорь решил, что простота правил — залог успеха, поэтому в его игре будет всего один тип фигур, кроме того, все фигуры в его игре одного цвета. Всевозможные ходы фигуры описываются множеством векторов смещений. В следующем абзаце находится формальное описание допустимых ходов.

Пусть горизонтали доски пронумерованы сверху вниз, а вертикали — слева направо от 1 до n. Сопоставим каждой клетке пару чисел (x, y) — номер соответствующей вертикали и горизонтали. Каждый из возможных ходов фигуры задается парой чисел (dx, dy), используя этот ход, фигура с поля (x, y) перемещается на поле (x + dx, y + dy). Ход можно совершить, если поле (x + dx, y + dy) находится внутри границ доски, и на нем нет другой фигуры. Фигуры, стоящие на полях, отличных от (x, y) и (x + dx, y + dy), не влияют на возможность совершения данного хода (например, как при ходе коня в обычных шахматах).

Игорь предлагает вам угадать, какие ходы может делать его фигура. Он расставил на доске несколько фигур и про каждое незанятое поле сообщил вам, находится ли оно под боем хотя бы одной фигуры (т.е. может ли какая-либо из стоящих на поле фигур сходить в это поле). Восстановите возможный набор ходов фигуры, либо определите, что Игорь ошибся и такая ситуация невозможна ни при каком наборе ходов.

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

В первой строке записано одно целое число n (1 ≤ n ≤ 50).

В следующих n строках записано по n символов, которые описывают предложенную Игорем позицию. j-й символ i-й строки может принимать значения:

  • o — в этом случае поле (i, j) занято фигурой, и поле может находиться либо не находиться под боем какой-то другой фигуры;
  • x — в этом случае поле (i, j) находится под боем какой-то из фигур;
  • . — в этом случае поле (i, j) не находится под боем ни одной из фигур.

Гарантируется, что на доске присутствует хотя бы одна фигура.

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

Если допустимое множество ходов существует, в первой строке выведите одно слово «YES» (без кавычек). Далее, выведите описание множества ходов фигуры в виде доски (2n - 1) × (2n - 1), в центре которой находится фигура, а символами 'x' отмечены атакуемые ею клетки, в формате, аналогичном формату ввода. Смотрите примеры вывода для полного понимания формата. Если существует несколько возможных вариантов ответа, выведите любой из них.

Если допустимого множества ходов не существует, выведите единственное слово «NO».

Примеры
Входные данные
5
oxxxx
x...x
x...x
x...x
xxxxo
Выходные данные
YES
....x....
....x....
....x....
....x....
xxxxoxxxx
....x....
....x....
....x....
....x....
Входные данные
6
.x.x..
x.x.x.
.xo..x
x..ox.
.x.x.x
..x.x.
Выходные данные
YES
...........
...........
...........
....x.x....
...x...x...
.....o.....
...x...x...
....x.x....
...........
...........
...........
Входные данные
3
o.x
oxx
o.x
Выходные данные
NO
Примечание

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