You are developing a simulation game where two factions battle on an $H \times W$ two-dimensional grid map.

Each cell in the grid can be represented by a pair of coordinates $(y, x)$. The cells in the first row are represented as $(0,0), (0,1), \dots, (0, W-1)$ from left to right, and the cells in the second row are represented as $(1,0), (1,1), \dots, (1, W-1)$. All cells up to the $H$-th row are represented by coordinates in the same manner. The cells above, below, to the left, and to the right of a given cell are called 'adjacent' to that cell.

The map consists of various terrains, and each terrain has a set 'ruggedness' value. Multiple units are placed on the map such that they do not overlap, and each unit belongs to one of the two warring factions. As long as a unit does not leave the map, it can move to an adjacent cell from its current position. Moving consumes stamina equal to the ruggedness of the terrain of the destination cell. Some terrains are too rugged, making movement impossible. If two units from different factions are adjacent, they are in a state of engagement.

All units have infinite stamina because they are well-supplied with combat rations. However, each unit has a limit on the total stamina it can consume in a single 'dash', which is called the unit's 'mobility'. A dash is a tactical action where a unit in combat moves quickly to a relatively nearby target point, passing through one or more cells. A dash is only possible if there is no other unit at the target point. If a unit encounters a unit of the same faction during a dash, it can pass through it; however, if it encounters a unit of a different faction, an engagement occurs the moment it becomes adjacent to that unit, so it must stop at that position. However, if the selected unit was already in a state of engagement, it can dash to escape the engagement.

You have created a bot that automatically selects an arbitrary unit and issues a dash command to test for bugs in the game. This bot sometimes issues impossible dash commands. A command is impossible if there is another unit at the target point, if the target point is impassable terrain, or if there is no path to the target point due to the mobility limit. If there are no bugs in the game, such commands should be ignored.

Now it is time to check if there are any bugs. Write a program that, given the commands issued by the bot in chronological order, outputs the coordinates of each unit after all commands have been processed sequentially.

Input

The first line contains the number of terrain types $N$, the height of the map $H$, and the width of the map $W$, separated by spaces ($1 \le N \le 9$, $2 \le H, W \le 500$).

The next $H$ lines contain $W$ integers separated by spaces, representing the terrain number of each cell from left to right, where each number is between $1$ and $N$ inclusive.

The next line contains $N$ integers $r_1, r_2, \dots, r_N$ ($-1 \le r_i \le 4$, $r_i \neq 0$) separated by spaces. If $r_i$ is $-1$, it means the $i$-th terrain is too rugged to enter; otherwise, $r_i$ represents the ruggedness of the $i$-th terrain.

The next line contains the number of units $M$ ($1 \le M \le H \times W / 4$).

The next $M$ lines contain four integers $m, t, a, b$ separated by spaces, representing the mobility, faction, $y$-coordinate, and $x$-coordinate of each unit, respectively, starting from unit 1 ($1 \le m \le 20$, $0 \le t \le 1$, $0 \le a < H$, $0 \le b < W$).

Each cell contains at most one unit, and no units are placed on impassable terrain.

The next line contains the number of dash commands $K$ ($1 \le K \le 10\,000$).

The next $K$ lines contain three integers $u, a, b$ separated by spaces, representing a dash command ($1 \le u \le M$, $0 \le a < H$, $0 \le b < W$). This is a command to dash unit $u$ to $(a, b)$.

Output

Output the positions of the units after all dash commands have been processed, over $M$ lines. If unit $i$ is located at $(a_i, b_i)$, output the two integers $a_i$ and $b_i$ separated by a space on the $i$-th line.

Examples

Input 1

3 5 5
1 1 3 3 2
3 3 3 1 2
1 1 1 2 1
2 2 1 1 1
1 1 1 1 3
1 3 -1
2
7 0 2 0
4 1 3 3
3
1 1 3
2 4 4
1 4 3

Output 1

4 3
3 3

Note

For the first dash command, if we do not consider hostile units, it could reach the target by moving along the path $(2,0) \to (2,1) \to (2,2) \to (2,3) \to (1,3)$. However, because of the hostile unit at $(3,3)$, an engagement occurs at $(2,3)$, so it cannot reach $(1,3)$, and since there is no path to bypass it without causing an engagement, it cannot be reached either. Therefore, this command is impossible and is ignored.

The second dash command is ignored because the target position is impassable terrain.

The third dash command can be performed by moving along the path $(2,0) \to (3,0) \to (4,0) \to (4,1) \to (4,2) \to (4,3)$, consuming 7 stamina. Since this value is not greater than the unit's mobility, it is a valid command.

Therefore, after all commands are processed, unit 1 is located at $(4,3)$ due to the last command, and unit 2 remains at its initial position.