Problem Description

It is June 20, 2022. To commemorate its 10th anniversary, AtCoder has built a garden in front of the company.
The garden is represented as a grid of $ H $ rows and $ W $ columns, where the cell at the $ i $-th row and $ j $-th column is referred to as cell $ (i, j) $.
Each cell contains one flower, and the beauty of the flower in cell $ (i, j) $ is $ A_{i, j} $.

For example, the following is an example of the garden, where the numbers in each cell represent the beauty of the flowers.

You want to prune some flowers to create a beautiful garden. A beautiful garden satisfies the following conditions:

• From any unpruned flower cell $ (a, b) $ to another unpruned flower cell $ (c, d) $, there is exactly one way to travel using only adjacent unpruned flower cells without revisiting any cell.
• This holds for all unpruned flower cells $ (a, b) $, $ (c, d) $ ($(a, b) \neq (c, d)$).

For example, the following pruning method results in a beautiful garden.

On the other hand, the following pruning method does not result in a beautiful garden.

The score of the garden is the sum of the beauty of the unpruned flowers. If the garden is not beautiful, the score is $ 0 $.
For example, the score of garden $ A $ in the figure is $ 20 $, garden $ B $ is $ 60 $, and the scores of gardens $ C $, $ D $, and $ E $ are $ 0 $.
Output a pruning method that maximizes the score of the garden.

Input Format

The input is given from the standard input in the following format:

$ H $ $ W $ $ A_{1, 1} $ $ A_{1, 2} $ $ A_{1, 3} $ ... $ A_{1, W} $ $ A_{2, 1} $ $ A_{2, 2} $ $ A_{2, 3} $ ... $ A_{2, W} $ $ A_{3, 1} $ $ A_{3, 2} $ $ A_{3, 3} $ ... $ A_{3, W} $ ... $ A_{H, 1} $ $ A_{H, 2} $ $ A_{H, 3} $ ... $ A_{H, W} $

Output Format

Output $ H $ lines in the following format:

$ c_{1, 1}c_{1, 2}c_{1, 3} ... c_{1, W} $ $ c_{2, 1}c_{2, 2}c_{2, 3} ... c_{2, W} $ $ c_{3, 1}c_{3, 2}c_{3, 3} ... c_{3, W} $ ... $ c_{H, 1}c_{H, 2}c_{H, 3} ... c_{H, W} $

Where $ c_{i, j} $ is # if the cell $ (i, j) $ is not pruned, and . if it is pruned.

Sample Input and Output

Sample Input #1

3 3
1 2 3
4 5 6
7 8 9

Sample Output #1

#.#
###
#.#

Sample Input #2

4 5
4 1 8 2 6
2 2 1 2 5
3 5 1 9 2
5 1 2 3 6

Sample Output #2

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

Notes/Hints

Constraints

• $ H, W $ are integers between $ 1 $ and $ 500 $ inclusive.
• $ A_{i, j} $ is an integer between $ 1 $ and $ 9 $ inclusive.

Test Case Generation

Test cases are generated as follows:

• For each test case, the values of $ H $ and $ W $ are determined. Refer to the sub-tasks and scores section for details.
• For each $ (i, j) $ ($1 \leq i \leq H, 1 \leq j \leq W$), $ A_{i, j} $ is chosen uniformly at random from integers between $ 1 $ and $ 9 $ inclusive.

Sub-tasks and Scores

There are $ 15 $ test cases used for scoring. Each test case is scored out of $ 100 $ points, and the total score for this problem is $100 \times 15 = 1500$ points.
The scoring method for each case is as follows, where $ L $ is the score of the garden, and $L' = L \div (H \times W)$.

(☆) For $ H = 5, W = 5 $ (cases $ 1, 2, 3 $) and $ H = 5, W = 500 $ (cases $ 4, 5, 6 $):

• $0.00 \leq L' < 2.00$: $ 0 $ points
• $2.00 \leq L' < 3.33$: $0 + (L - 2.00) \times 21$ points
• $3.33 \leq L' < 3.93$: $28 + (L - 3.33) \times 40$ points
• $3.93 \leq L' < 4.03$: $52 + (L - 3.93) \times 480$ points
• $4.03 \leq L'$: $ 100 $ points

(★) For $ H = 500, W = 500 $ (cases $ 7, 8, 9, 10, 11, 12, 13, 14, 15 $):

• $0.00 \leq L' < 2.00$: $ 0 $ points
• $2.00 \leq L' < 3.33$: $0 + (L - 2.00) \times 21$ points
• $3.33 \leq L' < 3.78$: $28 + (L - 3.33) \times 75$ points
• $3.78 \leq L' < 3.84$: $61 + (L - 3.78) \times 650$ points
• $3.84 \leq L'$: $ 100 $ points

The graph showing the relationship between $ L' $ and the score for $2.00 \leq L' \leq 4.05$ is as follows:

Note

Please note that a test case scoring $ 0 $ points will result in a WA verdict.
A WA verdict may still award points, and an AC verdict may not guarantee full points.

This problem is a marathon-style task, and it is not guaranteed that all cases can be solved for full points. The problem setter's solution may not necessarily achieve full points.
Additionally, if a significant number of submissions exceed the full point criteria, there is a very small chance that the scoring formula may be adjusted. Please understand this. However, no changes to the scoring will occur after 3 hours from the start of the contest.

Sample Explanation 1

Pruning as shown in Output Example 1 results in a garden score of $ 1 + 3 + 4 + 5 + 6 + 7 + 9 = 35 $ points. Note that this test case is not included in the scoring data.

Sample Explanation 2

This input example corresponds to the images in the problem statement. The output example corresponds to Example $ B $ in the problem statement, resulting in a garden score of $ 60 $. At that time, the value of $ L' $ is $60 \div 20 = 3.00$.
There are also outputs that result in a garden score of $ 62 $, but note that it is not necessary to output the method that maximizes the garden score. Note that this test case is also not included in the scoring data.

见题面 Input 部分

见题面 Output 部分