CF1254A.Feeding Chicken

Long is a huge fan of CFC (Codeforces Fried Chicken). But the price of CFC is increasing, so he decides to breed the chicken on his own farm.

His farm is presented by a rectangle grid with $r$ rows and $c$ columns. Some of these cells contain rice, others are empty. $k$ chickens are living on his farm. The number of chickens is not greater than the number of cells with rice on the farm.

Long wants to give his chicken playgrounds by assigning these farm cells to his chickens. He would like to satisfy the following requirements:

• Each cell of the farm is assigned to exactly one chicken.
• Each chicken is assigned at least one cell.
• The set of cells assigned to every chicken forms a connected area. More precisely, if two cells $(x, y)$ and $(u, v)$ are assigned to the same chicken, this chicken is able to walk from $(x, y)$ to $(u, v)$ by passing only its cells and moving from each cell to another cell sharing a side.

Long also wants to prevent his chickens from fighting for food. Hence he wants the difference between the maximum and the minimum number of cells with rice assigned to a chicken to be as small as possible. Please help him.

Long 是 CFC（Codeforces 炸鸡）的狂热粉丝。但由于 CFC 的价格不断上涨，他决定在自己的农场中自行养殖鸡肉。

他的农场由一个 $r$ 行 $c$ 列的矩形网格表示。其中一些格子种有水稻，其余为空地。农场中生活着 $k$ 只鸡，且鸡的数量不超过农场中种有水稻的格子总数。

Long 希望通过将农场中的格子分配给鸡来为它们提供游乐场。他希望满足以下要求：

• 农场中的每个格子恰好被分配给一只鸡；
• 每只鸡至少被分配到一个格子；
• 分配给每只鸡的所有格子构成一个连通区域。更准确地说：若两个格子 $(x, y)$ 和 $(u, v)$ 被分配给了同一只鸡，则该鸡必须能仅通过自己所属的格子、且每次只能移动到与其共享一条边的相邻格子，从 $(x, y)$ 走到 $(u, v)$。

Long 还希望防止鸡因争夺食物而发生争斗。因此，他希望所有鸡所分得的含水稻格子数中的最大值与最小值之差尽可能小。请帮助他实现这一目标。

Each test contains multiple test cases. The first line contains the number of test cases $T$ ($1 \le T \le 2 \cdot 10^4$). Description of the test cases follows.

The first line of each test case contains three integers $r$, $c$ and $k$ ($1 \leq r, c \leq 100, 1 \leq k \leq 62$), representing the size of Long's farm and the number of chickens Long has.

Each of the next $r$ lines contains $c$ characters, each is either "." or "R", representing an empty cell or a cell with rice. It is guaranteed that the number of chickens is not greater than the number of cells with rice on the farm.

It is guaranteed that the sum of $r \cdot c$ over all test cases does not exceed $2 \cdot 10^4$.

每个测试包含多个测试用例。第一行包含测试用例的数量 $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$。

For each test case, print $r$ lines with $c$ characters on each line. Each character should be either a lowercase English character, an uppercase English character, or a digit. Two characters should be equal if and only if the two corresponding cells are assigned to the same chicken. Uppercase and lowercase characters are considered different, so "A" and "a" belong to two different chickens.

If there are multiple optimal answers, print any.

对于每个测试用例，输出 $r$ 行，每行包含 $c$ 个字符。每个字符必须为一个小写英文字母、一个大写英文字母或一个数字。当且仅当两个对应单元格被分配给同一只鸡时，这两个字符才应相等。大写和小写字母被视为不同字符，因此 “A” 和 “a” 属于两只不同的鸡。

若存在多个最优解，输出任意一个即可。

These pictures explain the sample output. Each color represents one chicken. Cells filled with patterns (not solid colors) contain rice.

In the first test case, each chicken has one cell with rice. Hence, the difference between the maximum and the minimum number of cells with rice assigned to a chicken is $0$.

In the second test case, there are $4$ chickens with $3$ cells of rice, and $2$ chickens with $2$ cells of rice. Hence, the difference between the maximum and the minimum number of cells with rice assigned to a chicken is $3 - 2 = 1$.

In the third test case, each chicken has $3$ cells with rice.

In the last test case, since there are $62$ chicken with exactly $62$ cells of rice, each chicken must be assigned to exactly one cell. The sample output is one of the possible way.

这些图片解释了样例输出。每种颜色代表一只鸡。填充有图案（而非纯色）的格子中包含米饭。

在第一个测试用例中，每只鸡各自分得一个含米饭的格子。因此，分配给各只鸡的含米饭格子数的最大值与最小值之差为 $0$。

在第二个测试用例中，有 $4$ 只鸡各自分得 $3$ 个含米饭的格子，另有 $2$ 只鸡各自分得 $2$ 个含米饭的格子。因此，分配给各只鸡的含米饭格子数的最大值与最小值之差为 $3 - 2 = 1$。

在第三个测试用例中，每只鸡均分得 $3$ 个含米饭的格子。

在最后一个测试用例中，由于共有 $62$ 只鸡且恰好有 $62$ 个含米饭的格子，因此每只鸡必须恰好分配到一个格子。样例输出是其中一种可行方案。