Stones

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

Zenyk and Marichka have a rectangular board with \(n\) rows and \(m\) columns. Each cell can be either empty or contain a single stone. Initially, some cells contain a stone.

Zenyk and Marichka make a sequence of moves together. In one move, Marichka chooses any empty cell on the board and places a stone in it, and then Zenyk must place a stone in all of the following \(k\) cells below and \(k\) cells to the right. Note that all these cells must exist and be empty at the moment of the move.

Your task is to determine the minimum number of moves after which every cell of the table will contain a stone, or determine that this is impossible to achieve.

Input

The first line contains three integers \(n\), \(m\), and \(k\) — the number of rows and columns of the table, as well as how many cells down and to the right Zenyk processes on each move, respectively.

The next \(n\) lines each contain \(m\) numbers, 0 or 1, separated by spaces. The number 1 means that the corresponding cell initially already has a stone, and 0 means it does not.

Output

In the first line, output TAK if they can place a stone in every cell, otherwise output NI.

If the answer is positive, then in the next line output a single integer — the minimum number of moves.

Constraints

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

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

Samples

Input (stdin) сopy	Output (stdout) сopy
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

Input (stdin) сopy	Output (stdout) сopy
3 4 2 0 0 0 1 0 1 1 1 1 1 1 1	NI

Notes

In the first example, Zenyk and Marichka can first make a move at cell (2, 2), then at (1, 1).

In the second example, they cannot make a move.