Единственное отличие этой задачи от задачи D1 состоит в том, что в задаче D1 не нужно выводить способ построения ответа, но это необходимо делать в этой задаче.
Рассмотрим прямоугольную таблицу размера \(n \times m\) (из \(n\) строк и \(m\) столбцов). Значение \(n \cdot m\) является чётным числом.
Доминошка — это фигура из двух клеток, имеющих общую сторону. Доминошка является горизонтальной, если одна из клеток находится правее другой, или вертикальной, если одна из клеток находится выше другой.
В этой таблице необходимо разместить \(\frac{nm}{2}\) доминошек таким образом, чтобы ровно \(k\) из них были расположены горизонтально, остальные — вертикально. Доминошки не должны пересекаться, и на таблице не должно оставаться незанятых ячеек.
Выходные данные
Для каждого набора входных данных выведите:
- «NO», если невозможно расположить доминошки описанным способом;
- в противном случае в первой строке, соответствующей набору входных данных, выведите «YES», далее выведите \(n\) строк, каждая из которых содержит по \(m\) символов — описание расположения доминошек на таблице. Каждая ячейка таблицы должна быть помечена строчной буквой латинского алфавита таким образом, чтобы любые две имеющие общую сторону клетки были помечены одинаковыми буквами тогда и только тогда, когда на них размещена одна и та же доминошка. Иными словами, обе части одной доминошки должны быть помечены одинаковой буквой, но две доминошки, соседние по стороне, должны быть помечены разными буквами. Если существует несколько решений, выведите любое из них.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
8
4 4 2
2 3 0
3 2 3
1 2 0
2 4 2
5 2 2
2 17 16
2 1 1
|
YES
accx
aegx
bega
bdda
YES
aha
aha
YES
zz
aa
zz
NO
YES
aaza
bbza
NO
YES
bbaabbaabbaabbaay
ddccddccddccddccy
NO
|