| Codeforces Round 601 (Div. 1) |
|---|
| Закончено |
Лун — большой фанат 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$$$ клетки с рисом, каждая курица должна получить ровно одну клетку. Есть несколько возможных разбиений.
