Problem Description

Under a post on "Gulu Forum", several different people replied, and these comments form an $n \times m$ matrix.

The forum moderator prAB noticed that commenters' name colors have only three types: gray, purple, and brown. He decided to "use divine power" to make these comments look more neat. However, the forum owner CsO2 might remove his moderator role because he "abuses divine power" and makes the forum "notorious". Therefore, prAB can use divine power at most $k$ times. His divine power has two types:

• "Tyranny Warning": send one gray name into the shard, making it become a brown name.
• "Spare Someone": unban one brown name, making it become a gray name.

Since the administrators of "Gulu Forum" are supreme, he can do nothing about the purple names in the comments.

prAB believes that among these name colors, the size of the largest submatrix with the same color can represent how neat the comments under this post are. So he wants to know the maximum possible neatness after he finishes using his divine power.

Input Format

• The first line contains three integers $n, m, k$.
• The next $n$ lines each contain a string of length $m$, representing the color of each person's name in the comment matrix. B means brown, G means gray, and P means purple.

Output Format

• The first line outputs an integer, the maximum neatness.
• The next $n$ lines each output a string of length $m$, in the same format as in the Input Format, representing the color of each person's name after modification. If there are multiple solutions, output any one.

3 4 2
BBGB
GBBB
PGPP

8
BBBB
BBBB
PGPP

Hint

Constraints and Notes

For $100\%$ of the testdata, $1 \le n, m \le 500$, $0 \le k \le nm$. The character matrix contains only uppercase letters B, G, and P.

Translated by ChatGPT 5