Double Chocolate (or Double Choco) is a type of puzzle played on a grid. Some cells are colored white, others are colored gray, and some cells contain integers greater than or equal to 1. The player must divide the entire puzzle into one or more regions according to the following rules:

• Each region must contain exactly one connected component of white cells and one connected component of gray cells, and these two components must have the same shape. Shapes are considered identical if one can be transformed into the other by flipping or rotating (horizontally, vertically, or diagonally).
• Each region can contain at most one cell with an integer written in it. If such a cell exists, the area of each color (white and gray) in that region must be equal to that integer.

Below are examples of a Double Chocolate puzzle and its correct solution.

Below are examples of incorrect solutions.

1. The area of the white and gray parts of the region does not match the number in the region, or there are two or more numbers in one region.
2. The white and gray regions are not connected to each other.
3. Within a single region, the white cells are not connected to each other, or the gray cells are not connected to each other.
4. There is an unnecessary boundary between cells belonging to the same region.
5. The shapes of the white and gray regions belonging to the same region do not match.

Given a Double Chocolate puzzle and a proposed solution, check if the solution is correct.

Input

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

The following lines describe the Double Chocolate puzzle. The first $N$ lines provide the color of each cell, given as 1 (gray) or 0 (white). The next line contains $K$, the number of integers written in the puzzle. The next $K$ lines each contain the coordinates $r, c$ (row number, column number) and the integer $k$ written in that cell. A given Double Chocolate puzzle may have zero, one, or multiple correct solutions.

The subsequent lines provide the answer to the puzzle. The answer is given in the form of ASCII art of size $(2N+1) \times (2N+1)$, containing information only about how the puzzle is divided into regions. This drawing satisfies the following conditions:

• Characters at odd-numbered rows and odd-numbered columns represent the vertices of each square cell and are all +.
• Characters at even-numbered rows and even-numbered columns represent the interior of each square cell and are all ..
• Characters at odd-numbered rows and even-numbered columns represent horizontal boundaries; they are - if a boundary exists there, and . otherwise. The even-numbered characters in the first and last rows are all -.
• Characters at even-numbered rows and odd-numbered columns represent vertical boundaries; they are | if a boundary exists there, and . otherwise. The first and last characters of even-numbered rows are all |.

Output

Output 1 if the given answer is a correct solution to the given puzzle, and 0 otherwise.

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$ is even, $1 \le r, c \le N$