Задача G. Торанианхендж ≡

Условие

Планетарное Правительство торанианцев приняло решение о постройке масштабного комплекса скульптур в свою честь. Для этого на карте планеты был выделен прямоугольный участок, поверхность которого можно представить в виде таблицы W × H клеток, ориентированных вдоль сторон света.

Каждая клетка рассматриваемого участка может быть свободна для застройки и обозначаться символом '.' (ASCII 46), либо быть занята обелиском знаменитому торанианцу. Обелиски торанианцев строго симметричны либо вдоль направления восток-запад, либо вдоль направления север-юг, либо в обоих направлениях одновременно и обозначаются на карте как '|' (ASCII 124), '-' (ASCII 45) и '+' (ASCII 43) соответственно.

Каждая скульптура комплекса занимает одну клетку. Из эстетических соображений было решено, что расположение скульптур должно обеспечить выполнение следующих условий.

1. Cкульптуры, находящиеся в той же строке карты, что и любой обелиск, симметричный в направлении восток-запад, расположены симметрично относительно него.
2. Cкульптуры, находящиеся в том же столбце карты, что и любой обелиск, симметричный в направлении север-юг, расположены симметрично относительно него.
3. Для каждого обелиска, симметричного в направлении восток-запад, имеется хотя бы одна скульптура, находящаяся в той же строке.
4. Для каждого обелиска, симметричного в направлении север-юг, имеется хотя бы одна скульптура, находящаяся в том же столбце.

Требуется по данной карте участка составить план расположения скульптур или определить, что это невозможно.

Формат входного файла

В первой строке входного файла находятся числа W и H. В следующих H строках по W символов находится описание карты.

Формат выходного файла

Выходной файл должен содержать H строк по W символов в каждой — искомый план сооружения. При этом J-й символ I-й строки должен быть символом '#' (ASCII 35), если в данную клетку следует установить скульптуру, и '.' (ASCII 46) — в противном случае. Если решений несколько, выведите любое из них.

Если составить план невозможно, выходной файл должен содержать единственную строку NONE.

Ограничения

1 ≤ W, H ≤ 100.

Поле содержит не менее одного и не более 100 обелисков.

Примеры тестов

3 2
.|.
-..

.#.
#..

3 2
.||
-..

NONE

6 4
......
...|..
.-....
......

......
.#...#
......
.#....