Лун — большой фанат CFC (Codeforces Fried Chicken/жареные курицы Codeforces). Однако цена на CFC растет, поэтому он решил разводить куриц на собственной ферме.
Его ферму можно представить как прямоугольную сетку с \(r\) строками и \(c\) столбцами. Некоторые из этих клеток содержат рис, другие пусты. На ферме живут \(k\) куриц. Количество куриц не превышает количество клеток с рисом.
Лун хочет подарить своим курицам клетки с рисом. Он хотел бы удовлетворить следующие требования:
- Каждая клетка фермы должна быть отдана ровно одной курице.
- Каждая курица должна получить как минимум одну клетку.
- Набор клеток, отданных одной курице, должен образовать связную область. Другими словами, если две клетки \((x, y)\) и \((u, v)\) отданы одной и той же курице, эта курица может пройти от \((x, y)\) до \((u, v)\), проходя только свои клетки и перемещаясь из каждой клетки в другую, разделяющую одну сторону (то есть, связность «по стороне»).
Лун не хочет, чтобы его курицы боролись за еду. Поэтому он хочет, чтобы разница между максимальным и минимальным количеством клеток с рисом, отданных для одной курицы, была как можно меньше. Пожалуйста, помогите ему.
Выходные данные
Для каждого теста выведите \(r\) строк по \(c\) символов на каждой из них. Каждый символ должен быть либо буквой английского алфавита (либо прописной, либо строчной), либо цифрой. Два символа должны быть одинаковы тогда и только тогда, когда соответствующие клетки принадлежат одной и той же курице. Большие и маленькие буквы считаются различными, поэтому «A» и «a» принадлежат различным курицам.
Если существует несколько решений, выведите любое из них.
Примечание
Эти рисунки объясняют пример вывода. Каждый цвет представляет одну курицу. Клетки, заполненные узорами (не однотонные), содержат рис.
В первом примере каждая курица имеет одну клетку с рисом. Следовательно, разница между максимальным и минимальным количеством клеток с рисом, отданных для курицы, равна \(0\).
Во втором примере есть \(4\) курицы, у которых по \(3\) клетки с рисом, и \(2\) курицы с \(2\) клетками. Следовательно, разница между максимальным и минимальным количеством клеток с рисом, отданных для курицы, составляет \(3 - 2 = 1\).
В третьем примере каждая курица имеет \(3\) клетки с рисом. 
В последнем примере есть \(62\) курицы и ровно \(62\) клетки с рисом, каждая курица должна получить ровно одну клетку. Есть несколько возможных разбиений.
Примеры
| № | Входные данные | Выходные данные |
|
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
|
11122
22223
33333
aacc
aBBc
aBBc
CbbA
CbbA
CCAA
11114
22244
32444
33344
33334
abcdefghijklmnopqrstuvwxyzABCDE
FGHIJKLMNOPQRSTUVWXYZ0123456789
|