A. Кормление куриц
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Лун — большой фанат CFC (Codeforces Fried Chicken/жареные курицы Codeforces). Однако цена на CFC растет, поэтому он решил разводить куриц на собственной ферме.

Его ферму можно представить как прямоугольную сетку с $$$r$$$ строками и $$$c$$$ столбцами. Некоторые из этих клеток содержат рис, другие пусты. На ферме живут $$$k$$$ куриц. Количество куриц не превышает количество клеток с рисом.

Лун хочет подарить своим курицам клетки с рисом. Он хотел бы удовлетворить следующие требования:

  • Каждая клетка фермы должна быть отдана ровно одной курице.
  • Каждая курица должна получить как минимум одну клетку.
  • Набор клеток, отданных одной курице, должен образовать связную область. Другими словами, если две клетки $$$(x, y)$$$ и $$$(u, v)$$$ отданы одной и той же курице, эта курица может пройти от $$$(x, y)$$$ до $$$(u, v)$$$, проходя только свои клетки и перемещаясь из каждой клетки в другую, разделяющую одну сторону (то есть, связность «по стороне»).

Лун не хочет, чтобы его курицы боролись за еду. Поэтому он хочет, чтобы разница между максимальным и минимальным количеством клеток с рисом, отданных для одной курицы, была как можно меньше. Пожалуйста, помогите ему.

Входные данные

Во входных данных находятся несколько (один или более) наборов входных данных. В первой строке находится одно целое число $$$T$$$ ($$$1 \le T \le 2 \cdot 10^4$$$) — количество наборов входных данных. Далее следуют их описания.

Первая строка каждого набора содержит три целых числа $$$r$$$, $$$c$$$ и $$$k$$$ ($$$1 \leq r, c \leq 100, 1 \leq k \leq 62$$$), которые обозначают размер фермы Луна и количество его куриц.

Каждая из следующих $$$r$$$ строк содержит $$$c$$$ символов, либо «.», либо «R», которые обозначают пустую клетку и клетку с рисом. Гарантируется, что количество куриц не превосходит количество клеток с рисом.

Гарантируется, что сумма значений $$$r \cdot c$$$ по всем наборам входных данных в тесте не превосходит $$$2 \cdot 10^4$$$.

Выходные данные

Для каждого теста выведите $$$r$$$ строк по $$$c$$$ символов на каждой из них. Каждый символ должен быть либо буквой английского алфавита (либо прописной, либо строчной), либо цифрой. Два символа должны быть одинаковы тогда и только тогда, когда соответствующие клетки принадлежат одной и той же курице. Большие и маленькие буквы считаются различными, поэтому «A» и «a» принадлежат различным курицам.

Если существует несколько решений, выведите любое из них.

Пример
Входные данные
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
Выходные данные
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$$$ клетки с рисом, каждая курица должна получить ровно одну клетку. Есть несколько возможных разбиений.