## 1) Abridged problem statement

You have an infinite grid of cells, initially white. You will output an **H×W** rectangle of cells, coloring some cells **black** and leaving the rest **white**.

- **Black cells** form a single **figure** if they are **8-connected** (adjacent by side or corner).
- A **spot** is a **finite** maximal **4-connected** component of **white** cells (side-adjacent connectivity). "Finite" matters because white cells outside the H×W rectangle extend to infinity and are connected to border white cells.

Given **H, W, N**, construct an H×W drawing that contains **exactly N spots**, or output `Impossible`.

Output format uses:
- `.` for **black**
- `#` for **white**

Separate different test cases by an empty line.

---

## 2) Detailed editorial (explaining the provided solution)

### Key observations

1. **What counts as a spot?**
   Spots are **maximal 4-connected white components that are finite**.
   Any white cell touching the border can connect (through the border) to the infinite outside-white region, hence it is **not finite**. Therefore, **only white components entirely inside the border can be spots**.

2. **How to create many spots easily**
   If we place isolated **white** cells inside a sea of **black**, each isolated white cell is a separate finite 4-connected component → **one spot**.

   To ensure isolation under **4-neighbour** connectivity, we can use a **checkerboard pattern**: cells of the same parity `(i+j)%2` are never side-adjacent; they are separated by at least one cell in between orthogonally.

3. **Avoid the border**
   Even if a white cell is isolated, if it lies on the border it is connected to the infinite outside white region.
   So we only place spot-cells in the **interior**: rows `1..H-2`, cols `1..W-2`.

4. **Maximum number of spots achievable with this method**
   In the interior grid of size `(H-2)×(W-2)`, the checkerboard splits cells into two parities. If we choose one parity and make those cells white (isolated), the number of available isolated positions is:

   - `count[0]` = number of interior cells with even parity
   - `count[1]` = number of interior cells with odd parity

   We can choose the parity with the larger count, so:

   ```text
   max_spots = max(count[0], count[1])
   ```

   If `N > max_spots`, output `Impossible`.

5. **Ensuring the black cells are a "figure" (8-connected)**
   The solution outputs a grid that is **mostly black**, and turns exactly `N` interior cells to white (spots).
   Black cells remain abundant; with only a sparse set of removed cells (on one checkerboard parity), the remaining black cells in the H×W rectangle stay **8-connected** in all relevant cases used by this construction.

### Construction steps

For each test case:

1. Compute `count[0]` and `count[1]` over interior cells.
2. If `N > max(count)`: print `Impossible`.
3. Pick parity `p_choose` with the larger count.
4. Collect all interior positions `(i,j)` with `(i+j)%2 == p_choose` into a list `positions`.
5. Start with all cells black: `grid` filled with `.`.
6. For `k=0..N-1`, set `grid[positions[k]] = '#'` (white).
7. Print the grid.

### Complexity

- Interior scanning: `O(HW)` with `H,W ≤ 20`
- Output size: `O(HW)`
- Very fast for `T ≤ 100`.

---

## 3) C++ Solution

```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;
}
```

---

## 4) Python solution (same approach, with detailed comments)

```python
import sys

def solve_case(h: int, w: int, n: int) -> str:
    # We will place isolated WHITE cells '#' on a checkerboard parity inside the border.
    # All other cells will be BLACK '.'.
    #
    # Each chosen '#' will be 4-disconnected from other '#' cells (checkerboard),
    # and since we never place '#' on the border, each such component is finite:
    # thus each is a "spot".

    # Count interior parity cells
    count = [0, 0]
    for i in range(1, h - 1):
        for j in range(1, w - 1):
            count[(i + j) & 1] += 1

    max_n = max(count)
    if n > max_n:
        return "Impossible"

    # Pick parity with more available cells
    p_choose = 0 if count[0] >= count[1] else 1

    # Collect all interior positions of that parity
    positions = []
    for i in range(1, h - 1):
        for j in range(1, w - 1):
            if ((i + j) & 1) == p_choose:
                positions.append((i, j))

    # Start with all black cells '.'
    grid = [list("." * w) for _ in range(h)]

    # Place n white isolated cells '#'
    for k in range(n):
        i, j = positions[k]
        grid[i][j] = "#"

    # Convert grid to lines
    return "\n".join("".join(row) for row in grid)

def main():
    data = sys.stdin.read().strip().split()
    t = int(data[0])
    idx = 1

    out_parts = []
    for _ in range(t):
        h = int(data[idx]); w = int(data[idx + 1]); n = int(data[idx + 2])
        idx += 3
        out_parts.append(solve_case(h, w, n))

    # Separate test cases by one empty line
    sys.stdout.write("\n\n".join(out_parts))

if __name__ == "__main__":
    main()
```

---

## 5) Compressed editorial

Use isolated interior white cells as spots. A white spot must be finite, so no white cell may touch the border (border white connects to infinite outside). Place white cells on one checkerboard parity inside the interior `(1..H-2, 1..W-2)`; same-parity cells are never 4-adjacent, so each white cell is its own spot. The maximum number of spots is the larger of the two parity counts in the interior. If `N` exceeds that, output `Impossible`; otherwise output an all-black grid and flip any `N` of those parity positions to white.
