Internet Problem Solving Contest

• Easy input data set – E1
• Hard input data set – E2

Kamila loves to torment her friends. Her new diabolic idea is an evil implementation of a well-known single-player game: Minesweeper.

In Minesweeper the player is shown an r × c grid of cells and told a positive integer m: the number of hidden mines. Each cell contains either a mine or a number. The number written in a cell is the count of mines in adjacent cells (horizontally, vertically, and also diagonally).

Initially, the content of each cell is hidden. The player plays the game by taking actions. In each action the player either asks for a cell to be revealed, or marks a cell that is certain to contain a mine. If the player reveals a cell with a zero, all adjacent cells are revealed automatically – because we know they cannot contain a mine. If any of those cells contain zeros as well, the revealing continues with the neighbors of those cells, and so on. The figure below shows one possible final result of revealing a zero in the top left corner. (In the figure, cells with zeros are the flat cells without a number.)

The player wins the game by locating all m mines. In Kamila’s version of the game each incorrect action immediately loses the game. That is, there are two ways to lose the game: you lose if you reveal a cell with a mine, and you also lose if you mark a cell without a mine as a cell with a mine. Once you take an incorrect action, the game will reveal the locations of all mines as a proof that you made a mistake.

Where’s the evil, you ask? Well, this is how Kamila envisions the gameplay:

1. The player chooses the dimensions of the grid and the number of mines.
2. The player reveals some cell.
3. The game pretends to be nice and friendly: it reports that the player revealed a zero. Then, the game does the automatic additional reveals described above.
4. What the game actually does is that it carefully choses the revealed area and the digits shown on its boundary in such a way that the player will be unable to take a second action. More precisely, regardless of what second action the player takes, the game will always claim that they lost, and show a placement of mines that proves it.

Problem specification

You are given the dimensions r, c and the number m of mines. Rows of the grid are numbered 0 through r − 1 from top to bottom. Columns are numbered 0 through c − 1 from the left to the right.

You are also given the coordinates (a_r, a_c) of the first revealed cell.

Check whether this is a situation in which Kamila can carry out her evil plan. If yes, compute and return one possible proof. (This is described in more detail below.)

Input specification

The first line of the input file contains an integer t specifying the number of test cases. Each test case is preceded by a blank line.

Each test case consists of a single line containing five integers: r, c, m, a_r, and a_c.

In the easy subproblem E1 you may assume the following:

• 10 ≤ r, c ≤ 20
• rc/10 ≤ m ≤ 7rc/10 (i.e., mines cover between 10 and 70 percent of the grid)
• 2 ≤ a_r < r − 2 and 2 ≤ a_c < c − 2 (i.e., the first revealed cell is at least 2 from each side)

In the hard subproblem E2 you may assume the following:

• 1 ≤ r, c ≤ 20
• 2 ≤ rc
• 1 ≤ m < rc
• 0 ≤ a_r < r and 0 ≤ a_c < c

Output specification

If the given values are such that Kamila is unable to carry out her evil plan, output a single line with the string IMPOSSIBLE. Otherwise, output the following things:

• First, a line containing the number x of different configurations of mines you want to provide.
• Then, x configurations of mines, each with exactly m mines.

Each configuration of mines is a r × c matrix of characters, with ‘.’ (period) represening a cell without a mine and ‘*’ (asterisk) representing a cell with a mine.

The output must have the following properties:

• x ≤ rc
• For each of the x configurations of mines the cell (a_r, a_c) must reveal a zero when clicked.
• For each of the x configurations of mines the set of cells revealed by revealing (a_r, a_c) in step 3 of the game must be the same, and the numbers shown in those cells must also be the same.
• For each cell that is not revealed in step 3 of the game, there must be at least one of these x configurations that does and at least one other configuration that does not contain a mine in that cell.

Finding a solution with the smallest possible x is not necessary. Any valid solution will be accepted.

The output should not contain any blank lines.

Example

Input:

3

1 2 1 0 0

1 3 1 0 0

2 7 2 0 2

Output:

IMPOSSIBLE
IMPOSSIBLE
3
.....**
.......
......*
.....*.
.....*.
......*

The first example is too small. When the player reveals the cell (0, 0), we cannot show them a zero because then we won’t be able to place the mine anywhere.

The second example is still too small. When the player reveals the cell (0, 0), we can tell them that (0, 0) contains a zero and (0, 1) contains a one. However, we have no chance to be evil. Instead, the player will correctly determine that the only unrevealed cell (0, 2) contains the mine.

In the third example our evil game will reveal the board as follows:

00001??
00001??

Above, question marks represent unrevealed cells. In this situation the player is unable to make a second move: each unrevealed cell may contain a mine, but at the same time each unrevealed cell may be empty. Regardless of what action the player takes, we can always show them one of the configurations shown in example output as the proof that they lost.