Дано поле , то есть с строками и столбиками.
Казак Ус хочет раскрасить клетки, используя минимальное количество цветов. Однако он не хочет, чтобы существовали две клетки одинакового цвета, манхэттенская расстояние между которыми равно .
Напомним, что манхэттенское расстояние между двумя клетками и равно .
Найдите минимальное количество цветов, которые для этого необходимы, а также выведите раскрашенное поле.
Первая строка содержит три целых числа , , (, ) — количество строк, столбцов, фиксированное манхэттенское расстояние.
В первой строке выведите наименьшее необходимое количество цветов .
В каждом из следующих строк выведите чисел — номера цветов соответствующих ячеек таблицы ().
Если есть несколько возможных таблиц, то выведите любую из них.
В первом примере позиции (1,1) и (2,2) имеют цвет 0, а позиции (1,2) и (2,1) цвет 1. Между позициями (1,1) и (1,2) манхэттенская расстояние |1-1|+|1-2|=1. Поскольку k=1, то эти две позиции должны иметь разные цвета. А вот между позициями (1,2) и (2,1) расстояние |1-2|+|2-1|=2. Поэтому они могут иметь одинаковый цвет.
( баллов): ;
( баллов): ;
( баллов): ;
( баллов): ;
( баллов): — нечетное;
( баллов): без дополнительных ограничений.