Камінці

Обмеження: 2 сек., 256 МіБ

Зеник і Марічка мають прямокутну дошку із \(n\) рядків та \(m\) стовпців. Кожна клітинка може бути або пустою, або містити один камінець. Початково у деяких клітинках поставлено по камінцю.

Зеник і Марічка разом виконують послідовність ходів. За один хід Марічка вибрає довільну пусту клітинку дошки та ставить в неї камінець, а далі Зеник має поставити по камінцю в усі клітинки серед наступних \(k\) клітинок знизу та \(k\) клітинок справа. Зауважте, що усі ці клітинки повинні існувати та бути пустими на момент ходу.

Ваше завдання — визначити мінімальну кількість ходів, після яких у кожній клітинці таблиці буде по камінцю, або визначити, що цього неможливо достягнути.

Вхідні дані

У першому рядку задано три цілих числа \(n\), \(m\) та \(k\) — кількість радяків та стовпців таблиці, а також скільки клітинок вниз та вправо опрацьовує Зеник на кожному ході відповідно.

У наступних \(n\) рядках задано по \(m\) чисел 0 або 1 розділених пробілами. Число 1 означає, що у відповідній клітинці початково вже є камінець, а 0 — що нема.

Вихідні дані

У першому рядку виведіть TAK, якщо вони можуть розмістити по камінцю в кожну клітинку, в протилежному разі виведіть NI.

Якщо відповідь позитивна, то в наступному рядку виведіть одне ціле число — мінімальну кількість ходів.

Обмеження

\(1 \le n, m \le 100\),

\(0 \le k \le 100\).

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
5 4 2 0 0 0 1 0 0 0 0 0 0 1 1 1 0 1 1 1 1 1 1	TAK 2

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
3 4 2 0 0 0 1 0 1 1 1 1 1 1 1	NI

Примітки

У першому прикладі Зеник і Марічка можуть спочатку походити в клітинку (2, 2), потім в (1, 1).

У другому прикладі вони не можуть зробити ходу.