Единственное отличие этой задачи от задачи 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
|