Дано поле 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 бали): без додаткових обмежень.