p490.in1
======================
3
7 9 2
20 20 22
5 5 10

=================
p490.ans1
======================
#......##
#.#.....#
#.##.....
....####.
.#..##.#.
.#..##.#.
.#.......

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

Impossible

=================
p490.cpp
======================
#include <bits/stdc++.h>

using namespace std;

template<typename T1, typename T2>
ostream& operator<<(ostream& out, const pair<T1, T2>& x) {
    return out << x.first << ' ' << x.second;
}

template<typename T1, typename T2>
istream& operator>>(istream& in, pair<T1, T2>& x) {
    return in >> x.first >> x.second;
}

template<typename T>
istream& operator>>(istream& in, vector<T>& a) {
    for(auto& x: a) {
        in >> x;
    }
    return in;
};

template<typename T>
ostream& operator<<(ostream& out, const vector<T>& a) {
    for(auto x: a) {
        out << x << ' ';
    }
    return out;
};

int h, w, n;

void read() { cin >> h >> w >> n; }

void solve() {
    // The solution here is fairly simple after understanding the problem
    // statement. We want to have exactly n white connected component, but
    // instead for a h x w grid, we can try to see what's the largest number of
    // components and then fill some of them down to n with black cells. The key
    // observation is that in the white connected components we don't consider
    // diagonal neigbours, meaning we can try a chess board. There are two
    // candidates for a chess board, and we choose the one with more white
    // cells. We only place on inner positions (skip the border) because a
    // white cell on the border would connect to the infinite white exterior
    // and not form a finite spot.

    static bool first = true;
    if(!first) {
        cout << '\n';
    }
    first = false;

    array<int, 2> count = {0, 0};
    for(int i = 1; i < h - 1; i++) {
        for(int j = 1; j < w - 1; j++) {
            count[(i + j) % 2]++;
        }
    }

    int max_n = max(count[0], count[1]);
    if(n > max_n) {
        cout << "Impossible\n";
        return;
    }

    int p_choose = count[0] >= count[1] ? 0 : 1;

    vector<pair<int, int>> positions;
    for(int i = 1; i < h - 1; i++) {
        for(int j = 1; j < w - 1; j++) {
            if((i + j) % 2 == p_choose) {
                positions.emplace_back(i, j);
            }
        }
    }

    vector<string> grid(h, string(w, '.'));
    for(int k = 0; k < n; k++) {
        grid[positions[k].first][positions[k].second] = '#';
    }

    for(auto& row: grid) {
        cout << row << '\n';
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int T = 1;
    cin >> T;
    for(int test = 1; test <= T; test++) {
        read();
        solve();
    }

    return 0;
}

=================
statement.txt
======================
490. Figure ans Spots
Time limit per test: 0.25 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard



Let's consider an infinite sheet of grid paper. Initially all the cells are white and you can paint some of them black.

Two cells are called 8-neigbours if they share a side or a corner. An 8-path between black cells A and B is a sequence of cells X0 = A, X1, ·s, XL-1, XL = B such that all cells in the sequence are black and for all 0 ≤ i < L the cells Xi and Xi+1 are 8-neighbours. A set of black cells is called a figure if there is an 8-path from each of them into each other.

Two cells are called 4-neighbours if they share a side. A 4-path between white cells A and B is a sequence of cells X0 = A, X1, ·s, XL-1, XL = B such that all cells in the sequence are white and for all 0 ≤ i < L the cells Xi and Xi+1 are 4-neigbours. A finite set of white cells is called a  if:
There is a 4-path from each of them into each other.
The previous condition is broken when any other white cell is added to the set.
We say that a figure has the height H and the width W if it fits in a rectangle H rows high and W columns wide, but does not fit in a rectangle H-1 rows high and W columns wide nor in a rectangle H-1 rows high and W columns wide.




The image above shows a figure with height 7 and width 9 and containing two spots.

Given the numbers H, W and N, construct a figure with height exactly H and width exactly W and containing exactly N spots.

Input
The input file contains several test cases. The first line of the file contains T (1 ≤ T ≤ 100), the number of test cases. Each of the following T lines describes one test case and contains three integers H, W and N (1 ≤ H, W ≤ 20, 1 ≤ N ≤ 200), separated by spaces.

Output
The output file should contain the following data for each test case:
If it is possible to construct a figure with the given parameters, output any of the possible figures as H rows consisting of W characters each; output the character . for a black cell and the character # for a white cell.
If it is impossible to construct the required figure, output a single line containing the word .
The output data for two different test cases should be separated by an empty line.

Example(s)
sample input
sample output
3
7 9 2
20 20 22
5 5 10
#......##
#.#.....#
#.##.....
....####.
.#..##.#.
.#..##.#.
.#.......

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

Impossible

=================
