Cafe

Time limit2sMemory limit512 MB

Summary

Place exactly k chairs in an n by m grid so every chair touches at least one table in its 8 neighbors, or report impossibility.

Level: Medium6 of 10
Topics: Greedy, Implementation, Brute force, Math
Solved: No attempts yet

Problem

A summer cafe has the shape of a rectangle of $n\times m$ cells, and each cell can contain a table or a chair.

A banquet for $k$ people is planned at the cafe. For this, exactly $k$ chairs must be placed so that next to each chair (in one of the neighboring cells vertically, horizontally, or diagonally) there is a table. Help the cafe administrators solve this problem or report that it is impossible.

Input

The input file contains three numbers $n$ , $m$ , and $k$ ( $1 \le n, m \le 50$ , $1 \le k \le 10000$ ).

Output

The output file must contain $n$ lines of $m$ characters each: the plan for placing tables and chairs for the banquet. The character h denotes a chair, T denotes a table, and . denotes an empty cell. If there is no solution, output the line Impossible.

Examples2

Example 1
Input
```
3 4 8
```
Expected output
```
hhh.
hTTh
.hhh
```
Example 2
Input
```
2 2 4
```
Expected output
```
Impossible
```