비전 프로그램

로봇의 카메라가 사진을 찍을 때마다 그 이미지는 흑백 이미지로 로봇의 메모리에 저장된다. 각 이미지는 $H \times W$ 격자이며, 행은 0번부터 $H-1$번까지, 열은 0번부터 $W-1$번까지 번호가 매겨져 있다. 모든 이미지에는 검은 픽셀이 정확히 두 개 있고, 나머지 픽셀은 모두 흰색이다.

로봇은 간단한 명령어로 이루어진 프로그램으로 각 이미지를 처리할 수 있다. 주어진 $H$, $W$와 양의 정수 $K$에 대해, 임의의 이미지에서 두 검은 픽셀 사이의 거리가 정확히 $K$인지 판별하는 프로그램을 만들어 내는 절차를 작성하라. 행 $r_1$, 열 $c_1$의 픽셀과 행 $r_2$, 열 $c_2$의 픽셀 사이의 거리는 $|r_1-r_2|+|c_1-c_2|$이다. 여기서 $|x|$는 $x \geq 0$이면 $x$, $x < 0$이면 $-x$와 같다.

로봇의 메모리는 0번부터 번호가 붙은 충분히 큰 셀의 배열이다. 각 셀은 0 또는 1을 저장할 수 있으며, 한 번 설정된 값은 바뀌지 않는다. 이미지는 행 단위로 셀 0번부터 $H \cdot W - 1$번까지에 저장된다. 첫 번째 행은 셀 0번부터 $W-1$번까지에, 마지막 행은 셀 $(H-1) \cdot W$번부터 $H \cdot W - 1$번까지에 저장된다. 행 $i$, 열 $j$의 픽셀이 검은색이면 셀 $i \cdot W + j$의 값은 1이고, 그렇지 않으면 0이다.

로봇의 프로그램은 0부터 연속된 번호가 붙은 명령어의 나열이다. 명령어는 하나씩 차례로 실행된다. 각 명령어는 하나 이상의 셀 값(명령어의 입력)을 읽고, 0 또는 1의 값 하나(명령어의 출력)를 만든다. $i$번 명령어의 출력은 셀 $H \cdot W + i$번에 저장된다. $i$번 명령어의 입력으로는 셀 0번부터 $H \cdot W + i - 1$번까지만 쓸 수 있으며, 이 셀들은 픽셀이거나 이전 명령어의 출력이다.

명령어는 네 종류가 있다.

• NOT: 입력이 하나뿐이다. 입력이 0이면 출력은 1이고, 그렇지 않으면 0이다.
• AND: 입력이 하나 이상이다. 모든 입력이 1일 때에만 출력이 1이다.
• OR: 입력이 하나 이상이다. 입력 중 하나 이상이 1일 때에만 출력이 1이다.
• XOR: 입력이 하나 이상이다. 1인 입력의 개수가 홀수일 때에만 출력이 1이다.

마지막 명령어의 출력은 두 검은 픽셀 사이의 거리가 정확히 $K$이면 1이어야 하고, 그렇지 않으면 0이어야 한다.

• $1 \leq H \leq 200$
• $1 \leq W \leq 200$
• $2 \leq H \cdot W$
• $1 \leq K \leq H+W-2$