Homework
Contest: Russian Code Cup 2016 - Finals [Unofficial Mirror, Div. 1 Only Recommended]
Difficulty rating: 3100
Tags: constructive algorithms

Today Peter has got an additional homework for tomorrow. The teacher has given three integers to him: n, m and k, and asked him to mark one or more squares on a square grid of size n × m.

The marked squares must form a connected figure, and there must be exactly k triples of marked squares that form an L-shaped tromino — all three squares are inside a 2 × 2 square.

The set of squares forms a connected figure if it is possible to get from any square to any other one if you are allowed to move from a square to any adjacent by a common side square.

Peter cannot fulfill the task, so he asks you for help. Help him to create such figure.

Input format:
Input data contains one or more test cases. The first line contains the number of test cases t (1 ≤ t ≤ 100).

Each of the following t test cases is described by a line that contains three integers: n, m and k (3 ≤ n, m, n × m ≤ 105, 0 ≤ k ≤ 109).

The sum of values of n × m for all tests in one input data doesn't exceed 105.

Output format:
For each test case print the answer.

If it is possible to create such figure, print n lines, m characters each, use asterisk '*' to denote the marked square, and dot '.' to denote the unmarked one.

If there is no solution, print -1.

Print empty line between test cases.

Constraints:
Time limit: 3.0 s
Memory limit: 256.0 MB

Example input:
3
3 3 4
3 3 5
3 3 3

Example output:
.*.
***
.*.
**.
**.
*..
.*.
***
*..

Editorial:
The solution is constructive.
• First let us use backtracking to find solutions for all n, m < 5, it is also better to precalculate all answers, in order not to mess with non-asymptotic optimizations.
• Now m ≥ 5.
• Let us put asterisks from left to right, one row after another. When adding the new asterisk, we add 4 new L-trominoes, except the first asterisk in a row that adds 1 new L-tromino, and the last asterisk in a row adds 3 new L-trominoes. Let us stop when the number of remaining L-trominoes k is less than 4, or there are less than 5 free squares in the table.
• Now there are two cases   there is a free row  thee is no free row
• there is a free row
• thee is no free row
• If there is a free row, we stopped because k is now less then 4. So:   k = 0: the solution is found  k = 1: if there are already at least 2 asterisks in the current row, put the asterisk in the beginning of the next row, if there is only 1, put it in the end of the current row  k = 2, k = 3 — similar, left as an exercise.
• k = 0: the solution is found
• k = 1: if there are already at least 2 asterisks in the current row, put the asterisk in the beginning of the next row, if there is only 1, put it in the end of the current row
• k = 2, k = 3 — similar, left as an exercise.
• If there are now free rows left, one can see that you can only add k from the set {0, 1, 2, 3, 4, 5, 6, 8, 9, 12, 15} L-trominoes.
• And finally there is also the special case where the size of the board is 3 × m, m ≥ 5 and k = 2 * (m - 1) - 8 — in this case the first column should be left empty, and the rest of the board must be completely filled with asterisks.