Кольорова матриця

Дано поле $n\times m$, тобто з $n$ рядками та $m$ стовпчиками.

Козак вус хоче розфарбувати клітини, використовуючи мінімальну кількість кольорів. Проте він не хоче, щоб існували дві клітини однакового кольору, манхеттенська відстань між якими дорівнює $k$.

Нагадаємо, що манхеттенська відстань між двома клітинами $(x_1,y_1)$ та $(x_2,y_2)$ дорівнює $|x_1-x_2|+|y_1-y_2|$.

Знайдіть мінімальну кількість кольорів, які для цього потрібні, а також виведіть розфарбоване поле.

Input

Перший рядок містить три цілі числа $n$, $m$, $k$ ($1\le n,m,k\le 100$, $k<\min (n,m)$) — кількість рядків, стовпчиків, фіксована манхеттенська відстань.

Output

В першому рядку виведіть найменшу необхідну кількість кольорів $t$.

В кожному з наступних $n$ рядків виведіть $m$ чисел — номери кольорів відповідних клітинок таблиці ($0\le c_{i,j}\le t-1$).

Якщо є кілька можливих таблиць, то можна вивести будь-яку з них.

Examples

Note

У першому прикладі позиції (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. Тому вони можуть мати однаковий колір.

Scoring

1. ($17$ балів): $k=1$;

2. ($18$ балів): $k=2$;

3. ($14$ балів): $k=3$;

4. ($13$ балів): $k=4$;

5. ($24$ балів): $k$ — непарне;

6. ($14$ бали): без додаткових обмежень.