Killer Sudoku

A standard Sudoku puzzle is a $9 \times 9$ grid of squares filled in with the numbers 1 to 9, one number per square, so that each of the nine rows, nine columns and nine major sub-grids holds a permutation of the numbers 1 to 9. The major sub-grids are the nine $3 \times 3$ sub-grids that make up the overall $9 \times 9$ grid. A standard Sudoku puzzle starts with some numbers already placed in their squares, and the aim is to fill in the rest of the puzzle so that the row, column and major sub-grid constraints hold. Figure K.1 is a solved standard Sudoku.

Killer Sudoku is a variant on the standard form. Instead of starting with some individual numbers already placed, the grid is divided into one or more connected regions known as cages, and the numbers that may appear in a cage are constrained. Each cage has a total that the number or numbers in the cage must sum to. In the sub-variant considered here, the numbers in a cage must also be a set, so no number is repeated inside a cage.

Figure K.1: A standard Sudoku.

Figure K.2: A Killer Sudoku grid (left) with a solution (right).

You are given a completed grid. Check whether it meets the row, column, major sub-grid and cage constraints of this sub-variant. There is no guarantee that the cages in a grid make the grid soluble as a Killer Sudoku puzzle.

The input starts with a diagram of the grid. The diagram is a 19 by 37 array of characters.

The grid is a $9 \times 9$ grid of (not quite square) squares. A square, including its border, consists of 3 vertically aligned rows of 5 characters each. The border of each square is shared with the adjacent squares where they exist, and the border is filled in around the edge of the grid, as though the exterior were the boundary of an extra cage. The interior of each square is a row of 3 characters: a space, the integer $N$ ($1 \le N \le 9$) in the square, and another space.

The 4 border corners of a square are each a plus (+) character. Each border side between vertically adjacent squares is 3 characters between the corresponding corners. These 3 characters are all spaces if the two squares sharing the border are in the same cage, and all hyphens (-) otherwise. Each border side between horizontally adjacent squares is a single character, under one corner and above another. This character is a space if the squares sharing the border are in the same cage, and a vertical bar (|) otherwise.

+---+---+---+---+---+---+---+---+---+      +---+---+---+---+---+---+---+---+---+
| 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 |
+---+---+---+---+---+---+---+---+---+      +---+---+---+---+---+---+---+---+---+

Figure K.3: The general structure for the grid. Each 0 will be an integer from 1 to 9. The left is the minimal case with one large cage, and the right is the maximal case with 81 small cages.

The diagram is followed by one line for each cage in it. Each line contains three integers $R$ ($1 \le R \le 9$), $C$ ($1 \le C \le 9$) and $S$ ($1 \le S \le 45$). $R$ and $C$ give the row and the column of one square within the cage, and $S$ gives the value that the number or numbers within the cage must sum to.

The rows are numbered from 1 at the top to 9 at the bottom. The columns are numbered from 1 at the left to 9 at the right. The input contains exactly one constraint per cage.

Display OK if all of the constraints are met. Otherwise, display NotOK. There is no whitespace between Not and OK.

The grid of the first example is Figure K.2. The grid of the second example is Figure K.1 with the centre entry changed to a 4, and its cages match the major sub-grid constraints of a standard Sudoku.