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

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

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

다음은 오답의 예시이다.

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

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

Input

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

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

그 다음 줄부터는 해당 문제에 대한 답이 주어진다. 답은 $(2N+1) \times (2N+1)$ 크기의 아스키 아트 형태로 주어지며, 주어진 문제를 영역으로 나누는 방법에 대한 정보만을 포함한다. 이 그림은 다음의 조건을 만족한다.

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

Output

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

Examples

Input 1

4
0 0 0 1
1 1 1 1
0 1 0 1
0 1 0 0
2
3 2 3
4 1 1
+-+-+-+-+
|.......|
+-+-+-+.+
|.|...|.|
+.+.+.+.+
|.|...|.|
+-+-+.+-+
|...|...|
+-+-+-+-+

Output 1

1

Input 2

4
0 0 0 1
1 1 1 1
0 1 0 1
0 1 0 0
2
3 2 3
4 1 1
+-+-+-+-+
|...|...|
+.+.+-+-+
|...|...|
+-+-+.+.+
|...|...|
+.+.+.+.+
|...|...|
+-+-+-+-+

Output 2

0

Note

$2 \le N \le 10$, $N$은 짝수, $1 \le r, c \le N$