Ладья — шахматная фигура, которая может двигаться на любое число клеток по горизонтали или по вертикали при условии, что на её пути нет фигур. Ладья бьет шахматную фигуру, если фигура находится с ладьей на одной вертикали или горизонтали. В одной клетке шахматного поля может находится не более одной ладьи.
Вам даны $$$k$$$ ладей и шахматная доска с размером $$$n \times m$$$. Требуется расставить данные ладьи на этой доске так, чтобы они не били друг друга.
В единственной строке даны три натуральных числа $$$n$$$, $$$m$$$ и $$$k$$$ — размеры поля и число ладей, соответственно ($$$1 \le n, m, k \le 100$$$).
Если расставить $$$k$$$ ладей на поле $$$n \times m$$$ невозможно, выведите строку Impossible.
Если хотя бы одна искомая расстановка существует, выведите Possible. А затем выведите $$$n$$$ строк по $$$m$$$ символов в каждой — описание итоговой расстановки ладей на поле. В $$$i$$$-й строке $$$j$$$-м символом выведите «*», если клетка $$$(i, j)$$$ содержит ладью, и «.», если соответствующая клетка вашей расстановки пуста.
Если подходящих расстановок несколько, можно вывести любую из них.
1 2 1
Possible *.
3 3 100
Impossible
3 5 2
Possible ..*.. ..... *....
Иллюстрация расстановки ладьей для третьего теста из примера:
