Secret Message
Contest: Hello 2025
Difficulty rating: 3000
Tags: constructive algorithms, dfs and similar, math

Every Saturday, Alexander B., a teacher of parallel X, writes a secret message to Alexander G., a teacher of parallel B, in the evening. Since Alexander G. is giving a lecture at that time and the message is very important, Alexander B. has to write this message on an interactive online board.

The interactive online board is a grid consisting of $$$n$$$ rows and $$$m$$$ columns, where each cell is $$$1 \times 1$$$ in size. Some cells of this board are already filled in, and it is impossible to write a message in them; such cells are marked with the symbol ".", while the remaining cells are called free and are marked with the symbol "#".

Let us introduce two characteristics of the online board:

- $$$s$$$ is the number of free cells.
- $$$p$$$ is the perimeter of the grid figure formed by the union of free cells.

Let $$$A$$$ be the set of free cells. Your goal is to find a set of cells $$$S \subseteq A$$$ that satisfies the following properties:

- $$$|S| \le \frac{1}{5} \cdot (s+p)$$$.
- Any cell from $$$A$$$ either lies in $$$S$$$ or shares a side with some cell from $$$S$$$.

We can show that at least one set $$$S$$$ satisfying these properties exists; you are required to find any suitable one.

Input format:
The first line contains the number $$$t$$$ ($$$1 \le t \le 80\,000$$$) — the number of test cases.

In the first line of each test case, the numbers $$$n$$$ and $$$m$$$ ($$$1 \le n, m \le 2 \cdot 10^6$$$) — the dimensions of the grid are given.

The following $$$n$$$ lines contain the description of the grid.

It is guaranteed that the sum of $$$n \cdot m$$$ across all test cases does not exceed $$$2 \cdot 10^6$$$.

Output format:
For each test case, output $$$n$$$ lines consisting of $$$m$$$ symbols, where each symbol encodes the state of the cell:

- "#" — the cell is in $$$A$$$ but not in $$$S$$$;
- "S" — the cell is in both $$$A$$$ and $$$S$$$;
- "." — the cell is neither in $$$A$$$ nor in $$$S$$$.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first example, $$$s=5$$$ and $$$p=12$$$, thus the number of cells in $$$S$$$ must not exceed $$$\frac{1}{5} \cdot (5+12) = 3.4$$$, meaning $$$|S| \le 3$$$. Note that the presented set $$$S$$$ consists of $$$1$$$ cell and clearly satisfies all the constraints.

In the second example, $$$s=12$$$ and $$$p=16$$$, thus the number of cells in $$$S$$$ must not exceed $$$\frac{1}{5} \cdot (12+16)= 5.6$$$, meaning $$$|S| \le 5$$$. Note that the presented set $$$S$$$ consists of $$$4$$$ cells and clearly satisfies all the constraints.

In the third example, we will explain what perimeter is, as it may not be obvious. Any grid figure has a boundary, which can be represented as a union of segments that do not intersect at interior points. Thus, in the picture below, the thick black line denotes the boundary of the figure formed by the union of free cells. The total length of these segments is $$$p=24$$$.

At the same time, the value $$$s=11$$$ and the upper limit is $$$|S| \le 7$$$, the presented set has a size of $$$6$$$ and clearly satisfies all the constraints.

Example input:
3
3 3
.#.
###
.#.
2 6
######
######
3 7
###....
#.#.###
###....

Example output:
.#.
#S#
.#.
#S##S#
#S##S#
S#S....
#.#.S#S
S#S....

Editorial:
We will divide the infinite grid into $$$5$$$ sets of cells $$$L_1$$$, $$$L_2$$$, $$$L_3$$$, $$$L_4$$$, and $$$L_5$$$, where $$$L_i = \{ (x, y) \in \mathbb{Z}^2 \space | \space (x + 2 y) \equiv i \pmod{5} \}$$$. Note that for any pair $$$(x,y)$$$, all $$$5$$$ cells $$$(x,y)$$$, $$$(x-1, y)$$$, $$$(x+1, y)$$$, $$$(x, y-1)$$$, $$$(x, y+1)$$$ belong to different sets $$$L_1, \ldots, L_5$$$.
If we try to consider the sets $$$T_i = L_i \cap A$$$, it is not guaranteed that each of them will satisfy the property: "For each cell in the set $$$A$$$, either it or one of its neighboring cells shares a side belongs to the set $$$S$$$." Therefore, we denote $$$D_i \subseteq A$$$ as the set of cells from $$$A$$$ that do not belong to $$$T_i$$$ and all four neighbors of each of them also do not belong to $$$T_i$$$.
Now we need to verify the correctness of two statements:
• $$$|T_1| + |T_2| + |T_3| + |T_4| + |T_5| = s$$$;
• $$$|D_1| + |D_2| + |D_3| + |D_4| + |D_5| = p$$$;
The first statement is obvious since $$$T_1 \cup \ldots \cup T_5 = A$$$. The second statement is true because if some cell $$$(x, y)$$$ does not belong to $$$T_i$$$ and all its neighbors do not belong to $$$T_i$$$, it means that it has a neighbor $$$(x', y')$$$ such that $$$(x' + 2y') \bmod 5 = i$$$. But we know that $$$(x', y') \not \in A$$$, which means we can mark the shared side of $$$(x,y)$$$ and $$$(x', y')$$$. If we process $$$T_1, \ldots, T_5$$$ sequentially, then after this process, each segment of the boundary will be marked exactly once, and thus the number of such segments coincides with $$$|D_1| + \ldots + |D_5|$$$.
Now let $$$S_i = T_i \cup D_i$$$ and note that $$$|S_1| + \ldots + |S_5| = s + p$$$, which means, by the pigeonhole principle, there exists a $$$j$$$ such that $$$|S_j| \le \frac{1}{5} \cdot (s + p)$$$, and then $$$S_j$$$ will be suitable as the desired set.