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

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

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

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