Problem Description

A window of size $R \times S$ has several flies on it. There is a flyswatter that can eliminate all flies within a $K \times K$ rectangular area (excluding the boundary).

Choose a position to place the flyswatter such that the number of flies eliminated is maximized. Output the maximum number of flies that can be eliminated and the placement of the flyswatter. If there are multiple valid solutions, output any one.

Input Format

The first line contains three integers $R, S, K$.

The next $R$ lines, each containing $S$ characters, are either $\texttt{*}$ (indicating a fly) or $\texttt{.}$ (indicating an empty space). It is guaranteed that there is at least one fly that can be eliminated.

Output Format

The first line should output the maximum number of flies that can be eliminated. If only this value is correctly answered, you can get $50\%$ of the points.

The next $R$ lines should contain $S$ characters each. Based on the input matrix, modify the four corners of the chosen $K \times K$ rectangle to $\texttt{+}$, the horizontal edges to $\texttt{-}$, and the vertical edges to $\texttt{|}$. The chosen rectangle must be entirely within the matrix.

Sample Input and Output

Sample Input #1

3 5 3
.....
.*.*.
.....

Sample Output #1

1
+-+..
|*|*.
+-+..

Sample Input #2

7 6 4
......
.*.*.*
......
.*.*..
..*...
..*...
*....*

Sample Output #2

2
......
.*.*.*
+--+..
|*.|..
|.*|..
+--+..
*....*

Sample Input #3

9 9 6
***......
......*.*
.*....*..
..*...*..
..*.*....
..*....*.
.....*...
.*...***.
.........

Sample Output #3

6
***......
......*.*
.*....*..
..*+----+
..*|*...|
..*|...*|
...|.*..|
.*.|.***|
...+----+

Notes

[Data Range and Constraints]

• For $100\%$ of the data, $3 \le K \le R, S \le 100$.

[Hints and Notes]

Feel free to hack the custom Special Judge via private messages or posts.

This problem is translated from COCI 2015-2016 #7 Task 2 Prozor.

The score for this problem is set according to the original COCI problem, with a maximum score of $80$.

见题面 Input 部分

见题面 Output 部分