더블 초콜릿

Double Chocolate (또는 Double Choco)는 격자 위에서 이루어지는 퍼즐의 일종이다. 일부 칸은 흰색으로, 나머지는 회색으로 칠해져 있으며, 몇몇 칸에는 1 이상의 정수가 쓰여 있다. 플레이어는 퍼즐 전체를 다음의 규칙에 따라 1개 이상의 영역으로 나누어야 한다.

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

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

다음은 오답의 예시이다.

1. 영역의 흰색과 회색의 넓이가 영역 내의 수와 일치하지 않음, 한 영역 내에 수가 2개 이상 있음
2. 하나의 영역에 흰색 영역만 있거나 회색 영역만 있음
3. 하나의 영역 내에서 흰색 영역끼리, 회색 영역끼리 연결되어 있지 않음
4. 같은 영역에 속한 칸 사이에 불필요한 경계선이 있음
5. 같은 영역에 속한 흰색 영역과 회색 영역의 모양이 일치하지 않음

더블 초콜릿 문제와 답이 주어졌을 때, 정답이 맞는지 체크해보자.

첫 줄에 격자의 크기를 나타내는 정수 $N$이 주어진다. ($2 \le N \le 10$, $N$은 짝수)

다음 줄부터는 더블 초콜릿 문제가 주어진다. 첫 $N$개 줄에는 문제의 각 칸이 어떤 색인지 1(회색) 또는 0(흰색)으로 주어진다. 그 다음 줄에는 문제에 쓰여 있는 정수의 개수 $$가 주어지고, 그 다음 줄에는 각 줄마다 정수가 쓰여 있는 좌표 (행 번호, 열 번호)와 그 칸에 쓰여 있는 정수 가 순서대로 주어진다. 주어진 더블 초콜릿 문제는 정답이 0개, 1개, 또는 여러 개일 수 있다. (, )

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