Awkward Lights

You are working as a night watchman in an office building. Your task is to check whether all the lights in the building are turned off after all the office workers have left. If any lights are still on, you must turn them off. This task is not as easy as it sounds because of the strange behavior of the building's lighting system, described below. An electrical engineer inspected the system carefully but could not determine the cause of this behavior, so for now you have no choice but to keep relying on it.

Each floor of the building is a grid of square rooms. Every room has one light and one toggle switch. A toggle switch has two positions, but they do not correspond to fixed ON/OFF states. When the toggle switch of a room is flipped to its other position, the ON/OFF state of that room's light is reversed, and so are the lights of all rooms at a certain Manhattan distance from that room. The Manhattan distance between the room at $(x_1, y_1)$ and the room at $(x_2, y_2)$ is $|x_1 - x_2| + |y_1 - y_2|$.

For example, in a $4 \times 4$ grid, if the toggle switch of the room at $(2, 2)$ is flipped and the given Manhattan distance is two, then the lights of the rooms at $(1, 1)$, $(1, 3)$, $(2, 4)$, $(3, 1)$, $(3, 3)$, and $(4, 2)$, as well as at $(2, 2)$ itself, are reversed, as shown in Figure D.1, where black and white squares represent ON and OFF lights.

Figure D.1: An example of the lighting system's behavior.

Your task is to write a program that determines whether all the lights on a floor can be turned off.

The input is a sequence of datasets. Each dataset has the following format.

m n d
S11 S12 S13 ... S1m
S21 S22 S23 ... S2m
...
Sn1 Sn2 Sn3 ... Snm

The first line of a dataset contains three integers. $m$ and $n$ ($1 \le m \le 25$, $1 \le n \le 25$) are the numbers of columns and rows of the grid, respectively. $d$ ($1 \le d \le m + n$) is the Manhattan distance. The following $n$ lines each contain $m$ integers giving the initial ON/OFF states. Each $S_{ij}$ ($1 \le i \le n$, $1 \le j \le m$) is the initial state of the light in the room at $(i, j)$: 0 for OFF and 1 for ON.

The end of the input is indicated by a line containing three zeros.

For each dataset, output 1 if all the lights can be turned off, or 0 otherwise. Print the answer on its own line for each dataset.