Drone

There is a drone that can move only in the four directions: forward, backward, left, and right. The drone moves m in 1 second, and it always maintains an altitude of 1 m. The drone is just small enough to fit inside a 1 m2 square.

The drone carries an integer-recognition sensor. When an integer is located below the drone, the sensor displays it on an external billboard. The sensor can recognize only integers inside a red border.

Minsu built a maze the drone can move through. The maze floor is a square made of 1 m2 square tiles arranged in an N×N grid. Except for the entrance and the exit, the maze is surrounded by walls 2 m high. The entrance is always the left side of row 1, column 1, and the exit is always the right side of row N, column N. Inside the maze, there may be a wall 1 m wide and 2 m high between two tiles that share an edge.

All tiles in the maze are white, but some tiles are made of LEDs, so their borders can be changed to red when needed. They can of course be changed back to white as well. Each LED tile has one integer from 1 to N2 written on it. The maze may contain multiple LED tiles with the same number written on them.

Minsu devised a special racing game using the drone and the maze. Given a sequence s1, s2, ..., sT consisting of integers from 1 to N2, you must move the drone from the entrance to the exit so that the same sequence is displayed on the billboard. Assume that no two identical integers are consecutive. Also assume that the given sequence always allows the racing game to be finished. To keep a wrong sequence from appearing on the billboard, starting from s1, the borders of the LED tiles with the corresponding integer written on them are turned red in order; when the drone arrives and s1 is displayed on the billboard, the LED tiles turn white again, and now the borders of the LED tiles with s2 written on them turn red.

For example, <Figure 1> shows a maze made of 4×4 tiles. The entrance is marked by an arrow pointing in, and the drone is waiting just outside the entrance. The exit is marked by an arrow pointing out. The maze has 3 LED tiles, showing 1, 9, and 15 respectively.

When the sequence 1, 15, 9, 15 is given, first a red border appears on the tile at row 2, column 2 with the integer 1 written on it, and nothing is displayed yet on the billboard outside the maze (left of <Figure 2>). When the drone moves and arrives at the LED tile with 1 written on it, 1 is displayed on the billboard (middle of <Figure 2>), and now a red border appears on the tile at row 1, column 4 corresponding to the next number in the sequence, 15 (right of <Figure 2>).

After that, the drone moves and displays 15, 9, and 15 on the billboard, then exits through the exit, and the racing game ends. There can be several ways for the drone to move during the racing game. <Figure 3> shows one of those movement paths.

You must calculate and output the minimum time required for the racing game. The minimum time in the example above is 22, and <Figure 3> is the movement path for that time.

The first line gives the integer N, the size of the maze (1 ≤ N ≤ 500). Each of the following N lines gives N integers; each integer expresses the positions of the walls on the four sides of the corresponding tile in binary form as shown in <Figure 4>, and has a value from 0 to 15.

The next line gives the integer M, the number of LED tiles (1 ≤ M ≤ min{N2, 100}), and each of the following M lines gives the location of an LED tile as row xi, column yi (1 ≤ i ≤ M) and the integer ci written on the tile, in that order (1 ≤ xi, yi ≤ N, 1 ≤ ci ≤ N2).

The next line gives the integer T, the size of the sequence (1 ≤ T ≤ 1000), and the following line gives T integers sj (1 ≤ j ≤ T) (1 ≤ sj ≤ N2). Here, for every sj, there exists a ci such that sj = ci and the drone can reach the location of that LED tile. Also, for every sk (1 ≤ k < T), sk ≠ sk+1.

Output the minimum time required for the racing game as an integer.