题目描述

There is an urban myth that Peter the Great wanted to make a rectangular channel-grid engineering masterpiece not only from Vasilyevskiy island, but also from Kotlin island (where the town of Kronstadt is located nowadays).

The following mathematical model was (allegedly) presented to the tsar. The island is considered a rectangular grid $h$ cells high and $w$ cells wide. Each cell is dry land initially but can become water.

Technologies of those days allowed engineers to dig a channel across the entire island. In that case an entire row or an entire column of cells became water. If some of these cells already were water, their status did not change.

Your task is to propose a plan of the island which has exactly $n$ connected components of dry land cells.

输入格式

The only line of the input contains three integers $h , w$ , and $n$ -- grid's height, width and the desired number of connected components $(1 \le h , w \le 100$ ; $1 \le n \le 10^{9}).$

输出格式

If there is no valid plan containing $n$ connected components, output a single word Impossible.

Otherwise output $h$ lines of length $w$ depicting the plan. Dot $(‘. ')$ represents a dry land cell, hash (‘#') represents a water cell.

题目大意

对于一个 $h$ 行 $w$ 列的网格，每个格子都是“干燥的”。

你的每次操作可以把某一行或某一列的所有格子变成“湿润的”。

你的目标是在网格上留下恰好 $n$ 个由“干燥的”格子形成的连通块。

如果可以实现，请你输出一个 $h$ 行 $w$ 列的矩阵。 其中，用 . 表示“干燥的”格子， # 表示“湿润的”格子。

否则，输出一行一个 Impossible 表示不可能实现目标。

3 5 4

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

2 1 1

#
.

5 3 10

Impossible

提示

Time limit: 3 s, Memory limit: 512 MB.