Kotlin Island

Time limit3sMemory limit512 MB

Summary

Dig whole rows and columns of an h by w grid so the dry cells form exactly n connected components, printing the lexicographically smallest plan.

Level: Medium6 of 10
Topics: Greedy, Implementation, Combinatorics
Solved: No attempts yet

Problem

An urban myth says that Peter the Great wanted a rectangular grid of channels on Kotlin island, where the town of Kronstadt stands today, like the one on Vasilyevskiy island.

Engineers (allegedly) brought the tsar this mathematical model. The island is a rectangular grid $h$ cells high and $w$ cells wide, and every cell is dry land at the start. The technology of the day allowed them to dig a channel across the whole island, and one dig turns an entire row or an entire column into water. A cell that is already water stays water.

Two dry cells are joined when they share a side. A connected component is a maximal set of dry cells linked by such steps. Propose a plan of the island whose dry land has exactly $n$ connected components.

Input

The only line contains three integers $h$ , $w$ , and $n$ : the height of the grid, its width, and the desired number of connected components ( $1 \le h, w \le 100$ , $1 \le n \le 10^9$ ).

Output

If no plan has exactly $n$ connected components, print Impossible.

Otherwise print $h$ lines of $w$ characters each. A dot (.) is a dry land cell and a hash (#) is a water cell. Several plans can reach $n$ components, so print the lexicographically smallest one. Join the $h$ lines in order into a single string of $h \times w$ characters and compare those strings, treating # (ASCII 35) as smaller than . (ASCII 46).

Examples5

Example 1
Input
```
3 5 4
```
Expected output
```
##.#.
#####
##.#.
```
Example 2
Input
```
2 1 1
```
Expected output
```
#
.
```
Example 3
Input
```
5 3 10
```
Expected output
```
Impossible
```
Example 4
Input
```
1 1 1
```
Expected output
```
.
```
Example 5
Input
```
1 1 2
```
Expected output
```
Impossible
```