Double Chocolate

Double Chocolate (also called Double Choco) is a puzzle played on a grid. Some cells are white, the rest are gray, and some cells have an integer of 1 or greater written in them. The player must divide the whole puzzle into one or more regions that follow these rules.

• Each region contains exactly one connected area of white cells and one connected area of gray cells, where connected means joined up, down, left, or right. The two areas must have the same shape. Shapes that match after a flip or rotation, horizontal, vertical, or diagonal, count as the same shape.
• A region may contain at most one cell with a number. If it does, the area of each color in that region must equal that number.
• Two cells in the same region must not have an unnecessary border drawn between them.

The following is an example of a Double Chocolate problem and its correct answer.

The following is an example of a wrong answer.

• The white and gray areas of a region do not match the number in that region, or a region contains two or more numbers.
• A region contains only white cells or only gray cells.
• Within a region, the white cells or the gray cells are not connected to each other.
• Two cells in the same region have an unnecessary border between them.
• The white area and the gray area in the same region do not have the same shape.

Given a Double Chocolate problem and an answer, check whether the answer is correct.

The first line contains an integer N, the size of the grid.

The next N lines give the color of each cell, 1 for gray or 0 for white. The line after those contains K, the number of cells that have an integer. The next K lines each give the row r, the column c (row number, then column number), and the integer k written in that cell, in that order. The top-left cell is row 1, column 1. No coordinate appears twice.

After the problem comes the answer, a (2N+1) x (2N+1) ASCII art grid. It contains only information about how the problem is divided into regions. The grid satisfies these conditions.

• Characters at odd positions on odd lines are cell corners, and all of them are +.
• Characters at even positions on even lines are cell interiors, and all of them are ..
• Characters at even positions on odd lines mark horizontal borders. A border is - and no border is .. The first and last lines have - at every even position.
• Characters at odd positions on even lines mark vertical borders. A border is | and no border is .. The first and last characters of each even line are |.

Print 1 if the given answer is correct for the given problem, and 0 otherwise.

• $2 \le N \le 10$, $N$ is even
• $1 \le r, c \le N$, $1 \le k \le \frac{N^2}{2}$