Problem Description

In a fantasy world, there is a rectangular island. The island is divided into a grid with $R$ rows and $C$ columns.

Some cells are uninhabited, while some are occupied by exactly one of the following species: elves, humans, dwarves, or hobbits. The creatures occupying the same cell form a village in that cell.

To defend against demon attacks, they need to form alliances. Define the villages in the four adjacent directions (up, down, left, right) as the neighbors of a village.

Each species must satisfy the following requirements:

• Elves: only need to ally with one neighbor.
• Humans: need to ally with two neighbors, and these two neighbors cannot be in the up-down direction or the left-right direction.
• Dwarves: need to ally with three neighbors.
• Hobbits: need to ally with four neighbors (i.e., all neighbors).

Your task is to determine whether all villages on the island can ally with the required number of neighbors (some neighbors may end up not being allied). If yes, output the alliance structure. Otherwise output Impossible!.

Note: an alliance relationship is bidirectional.

Input Format

The first line contains two integers $r,c$.

The next $r$ lines each contain $c$ digits between $0\sim 4$, describing the population distribution of the island.

• 0: no village here.
• 1: this is an elf village.
• 2: this is a human village.
• 3: this is a dwarf village.
• 4: this is a hobbit village.

A useful trick: the input number corresponds to the number of alliances required at that cell.

Output Format

If it is impossible for all villages to form alliances, output Impossible!.

Otherwise, output a map in the following format:

Each cell is output as a $3\times 3$ matrix. If the cell is uninhabited, output . everywhere. If the cell has a village, output an O in the center. If this village forms alliances with some villages, output X in the four cells above, below, left, and right of O to indicate alliances.

All possible output patterns for each species are as follows:

(elves means elves, humans means humans, dwarves means dwarves, hobbits means hobbits)

If there are multiple solutions, output any one. This problem uses SPJ.

3 4
2 3 2 0
3 4 3 0
2 3 3 1

............
.OXXOXXO....
.X..X..X....
.X..X..X....
.OXXOXXO....
.X..X..X....
.X..X..X....
.OXXOXXOXXO.
............

1 2
2 1

Impossible!

Hint

Constraints

• For $55\%$ of the testdata, $\min(r,c)\le 10$ is guaranteed.
• For another $15\%$ of the testdata, $r\times c\le 20$ is guaranteed.
• For another $10\%$ of the testdata, the map contains only uninhabited areas and humans.
• For $100\%$ of the testdata, $1\le r,c\le 70$ is guaranteed.

Notes

This problem is translated from CEOI 2010 day 1 T1 alliances.

The translation copyright belongs to the problem provider

Translated by ChatGPT 5