D2. Домино (усложнённая версия)
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Единственное отличие этой задачи от задачи D1 состоит в том, что в задаче D1 не нужно выводить способ построения ответа, но это необходимо делать в этой задаче.

Рассмотрим прямоугольную таблицу размера $$$n \times m$$$ (из $$$n$$$ строк и $$$m$$$ столбцов). Значение $$$n \cdot m$$$ является чётным числом.

Доминошка — это фигура из двух клеток, имеющих общую сторону. Доминошка является горизонтальной, если одна из клеток находится правее другой, или вертикальной, если одна из клеток находится выше другой.

В этой таблице необходимо разместить $$$\frac{nm}{2}$$$ доминошек таким образом, чтобы ровно $$$k$$$ из них были расположены горизонтально, остальные — вертикально. Доминошки не должны пересекаться, и на таблице не должно оставаться незанятых ячеек.

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

В первой строке записано одно целое число $$$t$$$ ($$$1 \le t \le 10$$$) — количество наборов входных данных. Далее следуют $$$t$$$ наборов входных данных.

Каждый набор входных данных состоит из одной строки. Строка содержит три целых числа — $$$n$$$, $$$m$$$, $$$k$$$ ($$$1 \le n,m \le 100$$$, $$$0 \le k \le \frac{nm}{2}$$$, $$$n \cdot m$$$ — чётно) — количество строк, столбцов в таблице и горизонтальных доминошек соответственно.

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

Для каждого набора входных данных выведите:

  • «NO», если невозможно расположить доминошки описанным способом;
  • в противном случае в первой строке, соответствующей набору входных данных, выведите «YES», далее выведите $$$n$$$ строк, каждая из которых содержит по $$$m$$$ символов — описание расположения доминошек на таблице. Каждая ячейка таблицы должна быть помечена строчной буквой латинского алфавита таким образом, чтобы любые две имеющие общую сторону клетки были помечены одинаковыми буквами тогда и только тогда, когда на них размещена одна и та же доминошка. Иными словами, обе части одной доминошки должны быть помечены одинаковой буквой, но две доминошки, соседние по стороне, должны быть помечены разными буквами. Если существует несколько решений, выведите любое из них.
Пример
Входные данные
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