Hacking the Kangaroo Puzzle Randomizer

In the 2020 ICPC Nanjing Regional Contest, a randomized solution for the Kangaroo Puzzle problem was accepted. In that problem, a grid (or map) is given with dimensions \(n\) rows and \(m\) columns, where every cell is either empty or contains a wall. Initially, every empty cell contains exactly one kangaroo. When a control button (one of U, D, L, R) is pressed, each kangaroo will try to move one cell in that direction if and only if the adjacent cell exists and is empty at the beginning of the move. All moves are executed simultaneously. Thus, a move will only occur if the target cell, according to the current configuration, is empty. Multiple kangaroos may eventually merge if they move into the same cell.

Kotori submitted a solution that outputs a random control sequence of \(5 \times 10^4\) moves (each move chosen uniformly at random among U, D, L, and R). Your task is to construct an input map that will "hack" her solution. More precisely, the contest system has prepared 500 independently generated random move sequences. Your grid (which is used as input to the judging system) must meet the following conditions:

• The grid dimensions must satisfy \(1 \le n, m \le 20\).
• The grid must contain at least two empty cells.
• All empty cells must be reachable from any other empty cell (i.e. the graph of empty cells is connected).
• The empties must form a cycle-free graph (i.e. they form a tree structure).

After applying an entire random move sequence to the initial configuration (with one kangaroo per empty cell), if there remain at least two distinct cells occupied by kangaroos, then that run is considered a successful hack. Your input map must guarantee that at least 125 out of the 500 random sequences result in a failure to merge all kangaroos into one cell (i.e. a successful hack rate of at least 25%).

Note: You do not need to simulate the moves yourself. It is sufficient to output a legal grid map (in the format specified below) that you believe will achieve the hacking condition. One simple example is a grid consisting of 1 row and 2 columns (i.e. "1 2" on the first line and ".." on the second). In this map, because every move is blocked by the fact that each move would have a target cell that is occupied at the time of decision, no kangaroo ever moves and the initial configuration remains, ensuring a 100% hack success rate.

inputFormat

This problem does not take any input from standard input. Instead, your program should output a grid map that will be used as input for testing the randomized kangaroo control sequence.

The output format is as follows:

• The first line contains two space-separated integers \(n\) and \(m\) (\(1 \le n, m \le 20\)).
• The following \(n\) lines each contain a string of length \(m\). Use the character . to denote an empty cell and # to denote a wall.

Your grid must satisfy all the legal conditions mentioned in the problem statement.

outputFormat

Your program should output a legal grid map. For example, a valid output could be:

1 2
..

This output represents a grid with 1 row and 2 columns where both cells are empty.

sample

SampleTest1

1 2
..