你正在开发一款模拟游戏，两支势力在 $H \times W$ 的二维网格地图上进行战斗。

网格中的每个格子可以用坐标对 $(y, x)$ 表示。第一行的格子从左到右依次表示为 $(0,0), (0,1), \dots, (0, W-1)$，第二行的格子表示为 $(1,0), (1,1), \dots, (1, W-1)$。以此类推，直到第 $H$ 行的所有格子。某个格子的上、下、左、右相邻格子被称为该格子的“相邻”格子。

地图由多种地形组成，每种地形都有固定的“险峻度”数值。地图上分布着多个互不重叠的单位，每个单位属于交战双方中的一方。只要不出界，单位可以从当前位置移动到相邻格子。移动时，会消耗相当于目标格子地形险峻度的体力。某些地形过于险峻，可能无法通行。如果两个不同势力的单位相邻，则它们处于交战状态。

所有单位都携带了充足的战斗口粮，因此拥有无限的体力。但是，每个单位单次“突进”所能消耗的体力总量有限，这被称为单位的“移动力”。突进是战斗中的单位快速奔向相对较近的目标点并一次性移动的战术行为，移动路径包含一个或多个格子。只有当目标点没有其他单位时，突进才可能实现。在突进过程中，如果遇到同势力的单位，可以穿过；但如果遇到敌对势力的单位，一旦与该单位相邻，就会立即发生交战，因此必须停在该位置。不过，如果选定的单位本身已经处于交战状态，则可以通过突进脱离交战。

为了测试游戏是否存在 Bug，你制作了一个机器人，它会自动选择任意单位并下达突进指令。该机器人有时会下达无法执行的突进指令。如果目标点有其他单位、目标点为不可通行地形，或者由于移动力限制导致无法到达目标点，则该指令无法执行。如果游戏没有 Bug，这些指令应该被忽略。

现在是检查是否存在 Bug 的时候了。请编写一个程序，在给定按时间顺序排列的指令序列后，输出所有指令处理完毕后每个单位所在的坐标。

输入格式

第一行包含地形种类数 $N$、地图高度 $H$ 和地图宽度 $W$，以空格分隔。($1 \le N \le 9$, $2 \le H, W \le 500$)

接下来 $H$ 行，每行包含 $W$ 个整数，表示从左到右每个格子的地形编号，每个数值在 $1$ 到 $N$ 之间。

下一行包含 $N$ 个整数 $r_1, r_2, \dots, r_N$ ($-1 \le r_i \le 4, r_i \neq 0$)，以空格分隔。如果 $r_i$ 为 $-1$，表示第 $i$ 种地形过于险峻，无法进入；否则，$r_i$ 表示第 $i$ 种地形的险峻度。

下一行包含单位数量 $M$。($1 \le M \le H \times W / 4$)

接下来 $M$ 行，按单位编号 $1$ 到 $M$ 的顺序，每行包含四个整数 $m, t, a, b$，分别表示单位的移动力、所属势力、当前所在的 $y$ 坐标和 $x$ 坐标。($1 \le m \le 20, 0 \le t \le 1, 0 \le a < H, 0 \le b < W$)

每个格子最多放置一个单位，不可通行地形的格子上不会放置单位。

下一行包含突进指令的数量 $K$。($1 \le K \le 10\,000$)

接下来 $K$ 行，每行包含三个整数 $u, a, b$，表示将 $u$ 号单位突进至 $(a, b)$ 的指令。($1 \le u \le M, 0 \le a < H, 0 \le b < W$)

输出格式

输出 $M$ 行，表示所有突进指令处理完毕后单位的位置。如果 $i$ 号单位位于 $(a_i, b_i)$，则在第 $i$ 行输出两个整数 $a_i$ 和 $b_i$，以空格分隔。

样例

输入 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

输出 1

4 3
3 3

说明

对于第一个突进指令，如果不考虑敌对势力单位，可以通过路径 $(2,0) \to (2,1) \to (2,2) \to (2,3) \to (1,3)$ 到达。但由于 $(3,3)$ 处有敌对势力单位，在 $(2,3)$ 处会发生交战，因此无法到达 $(1,3)$，且没有其他不发生交战的绕行路径，因此该指令无法执行，被忽略。

第二个突进指令因目标位置是不可通行地形，无法执行，被忽略。

第三个突进指令可以通过路径 $(2,0) \to (3,0) \to (4,0) \to (4,1) \to (4,2) \to (4,3)$ 移动，消耗 $7$ 点体力。由于该值不大于单位的移动力，因此是可以执行的指令。

因此，所有指令处理完毕后，1 号单位因最后一条指令位于 $(4,3)$，2 号单位保持在初始位置。