Мирные ладьи

Ладья — шахматная фигура, которая может двигаться на любое число клеток по горизонтали или по вертикали.

Ладья может бить другую шахматную фигуру, если она находится на той же горизонтали или вертикали. Две шахматные фигуры не могут занимать одну клетку.

Есть шахматная доска размером N×M (N строк и M столбцов). Требуется на данном поле расставить K ладей так, чтобы они не били друг друга.

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

Первые три строки входного файла INPUT.TXT содержат три целых числа N, M и K – размеры поля и число ладей, соответственно (1 ≤ N, M, K ≤ 100).

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

В выходной файл OUTPUT.TXT выведите «Impossible» (без кавычек), если расставить K ладей на поле N×M невозможно.

Если хотя бы одна искомая расстановка существует, выведите в первой строке «Possible» (без кавычек). А затем выведите N строк по M символов в каждой – описание расстановки ладей на поле. В (i+1)-й строке j-м символом выведите «#», если клетка (i, j) содержит ладью, и «.», если соответствующая клетка вашей расстановки пуста. Если подходящих расстановок несколько, выведите любую.

Примеры

№	INPUT.TXT	OUTPUT.TXT	Пояснение
1	1 3 1	Possible .#.
2	2 3 4	Impossible	Невозможно на доске 2х3 разместить 4 ладьи без боя
3	3 5 2	Possible ..... #.... ...#.

Система оценки

Решения, работающие только для N, M ≤ 10, будут оцениваться в 25 баллов.

Для отправки решения задачи необходимо зарегистрироваться и авторизоваться!

[Обсуждение] [Все попытки] [Лучшие попытки] [Решение]