킬러 스도쿠

표준 스도쿠는 $9 \times 9$ 격자의 각 칸을 1부터 9까지의 숫자로 하나씩 채우는 퍼즐이다. 아홉 개의 가로줄, 아홉 개의 세로줄, 아홉 개의 작은 격자가 각각 1부터 9까지를 한 번씩 담아야 한다. 작은 격자는 전체 $9 \times 9$ 격자를 이루는 $3 \times 3$ 구역 아홉 개를 말한다. 표준 스도쿠는 몇몇 칸에 숫자가 미리 놓인 상태에서 시작하고, 세 조건을 지키면서 나머지 칸을 채우는 것이 목표다. 그림 K.1은 다 푼 표준 스도쿠다.

킬러 스도쿠는 표준 스도쿠의 변형이다. 숫자를 미리 놓는 대신 격자를 하나 이상의 연결된 구역으로 나누고, 그 구역을 케이지라고 부른다. 케이지마다 합이 하나씩 정해져 있고, 케이지 안의 숫자는 그 합을 이루어야 한다. 여기서 다루는 변형에서는 한 케이지 안의 숫자가 서로 달라야 한다.

그림 K.1: 표준 스도쿠.

그림 K.2: 킬러 스도쿠 격자(왼쪽)와 그 답(오른쪽).

숫자가 모두 채워진 격자가 주어진다. 이 격자가 가로줄, 세로줄, 작은 격자, 케이지 조건을 모두 지키는지 판정하라. 주어진 케이지 구성이 킬러 스도쿠 퍼즐로 풀리는 형태라는 보장은 없다.

입력의 처음에는 격자를 그린 그림이 주어진다. 그림은 19행 37열의 문자 배열이다.

격자는 칸 $9 \times 9$개로 이루어진다. 테두리를 포함한 한 칸은 세로로 놓인 세 줄이고, 각 줄은 문자 다섯 개다. 각 칸의 테두리는 이웃한 칸과 공유한다. 격자의 바깥 테두리는 바깥쪽이 또 하나의 케이지인 것처럼 모두 채워져 있다. 칸의 내부는 문자 세 개짜리 줄 하나로, 공백, 그 칸에 적힌 정수 $N$ ($1 \le N \le 9$), 공백 순서다.

한 칸의 네 모서리는 각각 더하기 기호(+)다. 세로로 인접한 두 칸 사이의 테두리는 두 모서리 사이의 문자 세 개로 나타낸다. 두 칸이 같은 케이지에 속하면 세 문자가 모두 공백이고, 다른 케이지에 속하면 모두 하이픈(-)이다. 가로로 인접한 두 칸 사이의 테두리는 문자 하나로 나타낸다. 이 문자는 두 칸이 같은 케이지에 속하면 공백이고, 다른 케이지에 속하면 세로 막대(|)다.

+---+---+---+---+---+---+---+---+---+      +---+---+---+---+---+---+---+---+---+
| 0   0   0   0   0   0   0   0   0 |      | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+   +   +   +   +   +   +   +   +   +      +---+---+---+---+---+---+---+---+---+
| 0   0   0   0   0   0   0   0   0 |      | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+   +   +   +   +   +   +   +   +   +      +---+---+---+---+---+---+---+---+---+
| 0   0   0   0   0   0   0   0   0 |      | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+   +   +   +   +   +   +   +   +   +      +---+---+---+---+---+---+---+---+---+
| 0   0   0   0   0   0   0   0   0 |      | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+   +   +   +   +   +   +   +   +   +      +---+---+---+---+---+---+---+---+---+
| 0   0   0   0   0   0   0   0   0 |      | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+   +   +   +   +   +   +   +   +   +      +---+---+---+---+---+---+---+---+---+
| 0   0   0   0   0   0   0   0   0 |      | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+   +   +   +   +   +   +   +   +   +      +---+---+---+---+---+---+---+---+---+
| 0   0   0   0   0   0   0   0   0 |      | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+   +   +   +   +   +   +   +   +   +      +---+---+---+---+---+---+---+---+---+
| 0   0   0   0   0   0   0   0   0 |      | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+   +   +   +   +   +   +   +   +   +      +---+---+---+---+---+---+---+---+---+
| 0   0   0   0   0   0   0   0   0 |      | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
+---+---+---+---+---+---+---+---+---+      +---+---+---+---+---+---+---+---+---+

그림 K.3: 격자의 전체 구조. 각 0 자리에는 1부터 9까지의 정수가 들어간다. 왼쪽은 큰 케이지 하나만 있는 최소 경우, 오른쪽은 작은 케이지 81개가 있는 최대 경우다.

그림 다음에는 그림에 있는 케이지마다 한 줄씩 주어진다. 각 줄에는 정수 $R$ ($1 \le R \le 9$), $C$ ($1 \le C \le 9$), $S$ ($1 \le S \le 45$)가 주어진다. $R$과 $C$는 이 케이지에 속한 칸 하나의 행과 열이고, $S$는 이 케이지의 숫자가 이루어야 할 합이다.

행은 위에서부터 1번, 열은 왼쪽에서부터 1번이다. 입력에는 케이지마다 조건이 정확히 하나씩 주어진다.

조건을 모두 지키면 OK를 출력한다. 그렇지 않으면 NotOK를 출력한다. Not과 OK 사이에 공백은 없다.

첫 번째 예제의 격자는 그림 K.2와 같다. 두 번째 예제의 격자는 그림 K.1의 한가운데 칸을 4로 바꾼 것이고, 케이지는 표준 스도쿠의 작은 격자 조건과 같다.