Дано поле n×m, то есть с n строками и m столбиками.
Казак Ус хочет раскрасить клетки, используя минимальное количество цветов. Однако он не хочет, чтобы существовали две клетки одинакового цвета, манхэттенская расстояние между которыми равно k.
Напомним, что манхэттенское расстояние между двумя клетками (x1,y1) и (x2,y2) равно ∣x1−x2∣+∣y1−y2∣.
Найдите минимальное количество цветов, которые для этого необходимы, а также выведите раскрашенное поле.
Первая строка содержит три целых числа n, m, k (1≤n,m,k≤100, k<min(n,m)) — количество строк, столбцов, фиксированное манхэттенское расстояние.
В первой строке выведите наименьшее необходимое количество цветов t.
В каждом из следующих n строк выведите m чисел — номера цветов соответствующих ячеек таблицы (0≤ci,j≤t−1).
Если есть несколько возможных таблиц, то выведите любую из них.
В первом примере позиции (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. Поэтому они могут иметь одинаковый цвет.
(17 баллов): k=1;
(18 баллов): k=2;
(14 баллов): k=3;
(13 баллов): k=4;
(24 баллов): k — нечетное;
(14 баллов): без дополнительных ограничений.