어색한 조명

당신은 어느 사무용 건물의 야간 경비원으로 일하고 있다. 당신의 임무는 건물 안의 모든 직원이 퇴근한 뒤 건물의 모든 조명이 꺼져 있는지 확인하는 것이다. 켜져 있는 조명이 있다면 반드시 그 조명을 꺼야 한다. 그런데 이 일은 생각만큼 쉽지 않은데, 아래에 설명하는 것처럼 이 건물의 조명 시스템이 이상하게 동작하기 때문이다. 전기 기술자가 시스템을 꼼꼼히 점검했지만 이런 동작의 원인을 밝혀내지 못했다. 그래서 당분간은 이 시스템에 계속 의존할 수밖에 없다.

건물의 각 층은 정사각형 방들이 격자 모양으로 배열되어 있다. 모든 방에는 조명 하나와 토글 스위치 하나가 있다. 토글 스위치는 두 가지 위치를 가지지만, 그 위치가 고정된 ON/OFF를 뜻하지는 않는다. 어떤 방의 토글 스위치를 다른 위치로 바꾸면, 그 방의 조명은 물론이고 그 방으로부터 특정 맨해튼 거리만큼 떨어진 방들의 조명 ON/OFF 상태도 함께 반전된다. 방 $(x_1, y_1)$과 방 $(x_2, y_2)$ 사이의 맨해튼 거리는 $|x_1 - x_2| + |y_1 - y_2|$이다.

예를 들어 $4 \times 4$ 격자에서 방 $(2, 2)$의 토글 스위치를 바꾸고 주어진 맨해튼 거리가 $2$라면, $(2, 2)$ 자신은 물론이고 $(1, 1)$, $(1, 3)$, $(2, 4)$, $(3, 1)$, $(3, 3)$, $(4, 2)$ 방들의 조명 상태가 반전된다. 이는 그림 D.1과 같으며, 검은 칸과 흰 칸은 각각 조명의 ON/OFF 상태를 나타낸다.

그림 D.1: 조명 시스템의 동작 예시.

당신의 임무는 한 층의 모든 조명을 끌 수 있는지 판정하는 프로그램을 작성하는 것이다.

입력은 여러 개의 데이터셋으로 이루어진다. 각 데이터셋의 형식은 다음과 같다.

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

데이터셋의 첫째 줄에는 세 정수가 주어진다. $m$과 $n$ ($1 \le m \le 25$, $1 \le n \le 25$)은 각각 격자의 열의 수와 행의 수이다. $d$ ($1 \le d \le m + n$)는 맨해튼 거리를 나타낸다. 이어지는 $n$개의 줄에는 각각 $m$개의 정수가 주어지며, 이는 초기 ON/OFF 상태이다. 각 $S_{ij}$ ($1 \le i \le n$, $1 \le j \le m$)는 방 $(i, j)$에 있는 조명의 초기 상태로, 0은 OFF, 1은 ON을 뜻한다.

입력의 끝은 세 개의 0으로 이루어진 줄로 표시된다.

각 데이터셋에 대해, 모든 조명을 끌 수 있으면 1을, 그렇지 않으면 0을 출력한다. 각 데이터셋마다 답을 한 줄에 출력한다.