Long 是 CFC(Codeforces 炸鸡)的忠实粉丝。但CFC的价格不断上涨,所以他决定在自己的农场饲养这只鸡。
他的农场由一个矩形网格呈现,其中包含 $$$r$$$ 行和 $$$c$$$ 列。其中一些单元格内装有大米,另一些单元格内是空的。他的农场里养着 $$$k$$$ 鸡。鸡的数量不大于农场里有稻米的小区数量。
Long 希望通过将这些农场单元分配给他的鸡来为他的鸡提供游乐场。他希望满足以下要求:
- 农场的每个单元都被分配给一只鸡。
- 每只鸡至少被分配一个单元格。
- 分配给每只鸡的一组单元格形成一个连通区域。更准确地说,如果将两个单元格 $$$(x, y)$$$ 和 $$$(u, v)$$$ 分配给同一只鸡,则这只鸡能够通过仅传递其单元格并从每个单元格移动到共享一侧的另一个单元格,从 $$$(x, y)$$$ 走到 $$$(u, v)$$$。
Long 还想防止他的鸡争夺食物。因此,他希望分配给鸡的最大和最小细胞数之间的差异尽可能小。请帮助他。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$T$$$ ($$$1 \le T \le 2 \cdot 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含三个整数 $$$r$$$、$$$c$$$ 和 $$$k$$$ ($$$1 \leq r, c \leq 100, 1 \leq k \leq 62$$$),代表 Long 农场的大小和 Long 拥有的鸡的数量。
接下来的 $$$r$$$ 行都包含 $$$c$$$ 字符,每个字符都是“.”。或“R”,代表空单元格或装有大米的单元格。保证鸡的数量不大于农场内有稻米的小区数量。
保证所有测试用例的 $$$r \cdot c$$$ 总和不超过 $$$2 \cdot 10^4$$$。
输出
对于每个测试用例,打印 $$$r$$$ 行,每行包含 $$$c$$$ 字符。每个字符应该是小写英文字符、大写英文字符或数字。当且仅当两个相应的单元格分配给同一只鸡时,两个字符才应该相等。大写和小写字符被认为是不同的,因此“A”和“a”属于两只不同的鸡。
如果有多个最佳答案,则打印其中一个。
示例
输入 #1
4 3 5 3 ..R.. ...R. ....R 6 4 6 R..R R..R RRRR RRRR R..R R..R 5 5 4 RRR.. R.R.. RRR.. R..R. R...R 2 31 62 RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR RRRRRRRRRRRRRRRRRRRRRRRRRRRRRRR
输出 #1
11122 22223 33333 aacc aBBc aBBc CbbA CbbA CCAA 11114 22244 32444 33344 33334 abcdefghijklmnopqrstuvwxyzABCDE FGHIJKLMNOPQRSTUVWXYZ0123456789
注意
这些图片解释了示例输出。每种颜色代表一只鸡。充满图案(非纯色)的单元格中含有大米。
在第一个测试用例中,每只鸡都有一个装有大米的细胞。因此,分配给鸡的最大和最小稻米单元数之间的差异为 $$$0$$$。
在第二个测试用例中,有 $$$4$$$ 鸡带有 $$$3$$$ 稻米细胞,$$$2$$$ 鸡带有 $$$2$$$ 稻米细胞。因此,分配给一只鸡的最大和最小稻米单元格数量之差为 $$$3 - 2 = 1$$$。
在第三个测试用例中,每只鸡都有 $$$3$$$ 细胞和大米。
在最后一个测试用例中,由于有 $$$62$$$ 只鸡恰好有 $$$62$$$ 个大米单元格,因此必须将每只鸡恰好分配给一个单元格。样本输出是可能的方式之一。