Задача C. Поворот блоков

Автор:И. Олейников   Ограничение времени:2 сек
Входной файл:input.txt   Ограничение памяти:2 Мб
Выходной файл:output.txt  

Условие

На строительную площадку завезли несколько больших прямоугольных бетонных блоков разных размеров.

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

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

При этом после поворота блоки не должны накладываться друг на друга или выходить за границу стройплощадки (соприкосновение блоков разрешается).

Изображение строительной площадки представляет собой квадрат размером N x N клеток. Каждая клетка либо пуста ('.'), либо занята частью блока ('#'). Требуется по изображению стройплощадки до начала работы крана определить, как она будет выглядеть после поворота максимально возможного количества блоков.

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

В первой строке входного файла задано число N, далее следует N строк по N символов в каждой — описание стройплощадки.

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

В выходной файл должно быть выведено изображение стройплощадки после окончания поворотов.

Ограничения

1 ≤ N ≤ 50, до поворота блоки не соприкасаются.

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

Входной файл (input.txt) Выходной файл (output.txt)
1
5
.....
.##..
.##..
.##..
.....
.....
.###.
.###.
.....
.....

0.086s 0.013s 13