Единственное отличие этой задачи от задачи D1 состоит в том, что в задаче D1 не нужно выводить способ построения ответа, но это необходимо делать в этой задаче.
Рассмотрим прямоугольную таблицу размера \(n \times m\) (из \(n\) строк и \(m\) столбцов). Значение \(n \cdot m\) является чётным числом.
Доминошка — это фигура из двух клеток, имеющих общую сторону. Доминошка является горизонтальной, если одна из клеток находится правее другой, или вертикальной, если одна из клеток находится выше другой.
В этой таблице необходимо разместить \(\frac{nm}{2}\) доминошек таким образом, чтобы ровно \(k\) из них были расположены горизонтально, остальные — вертикально. Доминошки не должны пересекаться, и на таблице не должно оставаться незанятых ячеек.