더블 초콜릿

더블 초콜릿(Double Choco)은 격자 위에서 푸는 퍼즐이다. 일부 칸은 흰색, 나머지 칸은 회색으로 칠해져 있고, 몇몇 칸에는 1 이상의 정수가 쓰여 있다. 플레이어는 퍼즐 전체를 다음 규칙을 지키며 1개 이상의 영역으로 나눠야 한다.

• 하나의 영역에는 상하좌우로 연결된 흰색 칸 영역과 회색 칸 영역이 하나씩 있어야 하며, 두 영역의 모양은 같아야 한다. 가로, 세로, 대각선으로 뒤집거나 회전해서 겹치는 모양도 같은 모양이다.
• 하나의 영역에는 정수가 쓰인 칸을 최대 1개만 포함할 수 있다. 그런 칸이 있으면 그 영역의 흰색 면적과 회색 면적이 각각 그 정수와 같아야 한다.
• 같은 영역에 속한 두 칸 사이에 불필요한 경계선이 그려져 있으면 안 된다.

다음은 더블 초콜릿 문제와 정답의 예시이다.

다음은 오답의 예시이다.

• 영역의 흰색 면적과 회색 면적이 영역 안의 정수와 일치하지 않거나, 한 영역 안에 정수가 2개 이상 있다.
• 한 영역에 흰색 영역만 있거나 회색 영역만 있다.
• 한 영역 안에서 흰색 영역끼리, 회색 영역끼리 연결되어 있지 않다.
• 같은 영역에 속한 칸 사이에 불필요한 경계선이 있다.
• 같은 영역에 속한 흰색 영역과 회색 영역의 모양이 일치하지 않는다.

더블 초콜릿 문제와 답이 주어졌을 때, 그 답이 정답인지 확인하라.

첫 줄에 격자의 크기를 나타내는 정수 N이 주어진다.

다음 N줄에는 각 칸의 색이 주어진다. 1은 회색, 0은 흰색이다. 그 다음 줄에는 정수가 쓰인 칸의 개수 K가 주어진다. 이어서 K줄에 각각 행 번호 r, 열 번호 c, 그 칸에 쓰인 정수 k가 이 순서대로 주어진다. 맨 왼쪽 위 칸은 1행 1열이다. 같은 좌표가 두 번 나오지 않는다.

문제 다음에는 답이 (2N+1) x (2N+1) 크기의 아스키 아트로 주어진다. 답에는 문제를 영역으로 나눈 방법에 대한 정보만 들어 있다. 이 그림은 다음 조건을 만족한다.

• 홀수 번째 줄의 홀수 번째 글자는 칸의 꼭짓점이며, 모두 +이다.
• 짝수 번째 줄의 짝수 번째 글자는 칸의 내부이며, 모두 .이다.
• 홀수 번째 줄의 짝수 번째 글자는 가로 경계선을 나타낸다. 경계선이 있으면 -, 없으면 .이다. 첫 번째 줄과 마지막 줄의 짝수 번째 글자는 모두 -이다.
• 짝수 번째 줄의 홀수 번째 글자는 세로 경계선을 나타낸다. 경계선이 있으면 |, 없으면 .이다. 짝수 번째 줄의 첫 번째와 마지막 글자는 모두 |이다.

주어진 답이 주어진 문제의 정답이면 1, 아니면 0을 출력한다.

• $2 \le N \le 10$, N은 짝수
• $1 \le r, c \le N$, $1 \le k \le \frac{N^2}{2}$