あなたは $H \times W$ サイズの2次元グリッドマップ上で、2つの勢力が戦闘を繰り広げるシミュレーションゲームを開発している。

グリッドの各マスは、$y$ 座標と $x$ 座標のペア $(y, x)$ で表すことができる。1行目のマスは左から順に $(0,0), (0,1), \dots, (0, W-1)$ と表し、2行目のマスは $(1,0), (1,1), \dots, (1, W-1)$ と表す。同様の方法で $H$ 行目までのすべてのマスを座標で表す。あるマスの上下左右のマスを、そのマスに「隣接した」マスと呼ぶ。

マップは多様な地形で構成されており、各地形は定められた「険しさ」の数値を持つ。また、マップには複数のユニットが互いに重ならないように配置されており、各ユニットは戦闘中の2つの勢力のいずれか一方に属する。各ユニットは、マップの外に出ない限り、現在位置から隣接するマスへ移動できる。移動時には、そのマスの地形が持つ険しさの分だけスタミナを消費する。一部の地形は非常に険しく、移動が不可能な場合もある。勢力の異なる2つのユニットが隣接していれば、その2つは交戦状態である。

すべてのユニットは戦闘食料を十分に持っているため、無限のスタミナを持っている。ただし、各ユニットは1回の「躍進（やくしん）」で消費できるスタミナの総量に制限があり、これをユニットの「移動力」と呼ぶ。躍進とは、戦闘中のユニットが比較的近い目的地まで素早く駆け抜けて一気に移動する戦術行動であり、1つ以上のマスを経由して移動することである。躍進は、目的地に他のユニットが存在しない場合にのみ可能である。躍進中に同じ勢力のユニットに出会った場合は通り抜けることができるが、異なる勢力のユニットに出会った場合は、そのユニットと隣接した瞬間に交戦が発生するため、その場で停止しなければならない。ただし、選択されたユニットがすでに交戦状態であった場合は、躍進して交戦から離脱することができる。

あなたはゲームにバグがないかテストするために、自動的に任意のユニットを選択して躍進命令を下すボットを作成した。このボットは実行不可能な躍進命令を下すこともある。目的地に他のユニットがいる場合、目的地が移動不可の地形である場合、または移動力の制限により目的地に到達する経路が存在しない場合、その命令は実行不可能である。ゲームにバグがなければ、このような命令は無視されなければならない。

今、バグがあるかどうかを確認する時間である。ボットが下した命令が時系列順に与えられたとき、すべての命令が順次処理された後の各ユニットの座標を出力するプログラムを作成せよ。

入力

1行目に地形の種類数 $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番のユニットから順に、各ユニットの移動力、勢力、ユニットがいるマスの $y$ 座標、ユニットがいるマスの $x$ 座標を意味する4つの整数 $m, t, a, b$ が空白区切りで与えられる。$(1 \le m \le 20, 0 \le t \le 1, 0 \le a < H, 0 \le b < W)$

各マスには最大1つのユニットが配置され、進入不可能な地形のマスにはユニットは配置されない。

次の行に躍進命令の数 $K$ が与えられる。$(1 \le K \le 10\,000)$

続いて $K$ 行にわたり、躍進命令を意味する3つの整数 $u, a, b$ が空白区切りで与えられる。$(1 \le u \le M, 0 \le a < H, 0 \le b < W)$ これは $u$ 番のユニットを $(a, b)$ へ躍進させる命令である。

出力

$M$ 行にわたり、すべての躍進命令が処理された後のユニットの位置を出力する。$i$ 番のユニットが $(a_i, b_i)$ に位置する場合、$i$ 番目の行に2つの整数 $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番目の躍進命令は、目的地が移動不可の地形であるため実行不可能であり、無視される。

3番目の躍進命令は、$(2,0) \to (3,0) \to (4,0) \to (4,1) \to (4,2) \to (4,3)$ の経路で動けば7のスタミナを消費して移動できる。これはユニットの移動力より大きくない値であるため、実行可能な命令である。

したがって、すべての命令が処理された後、1番のユニットは最後の命令により $(4,3)$ に位置し、2番のユニットは初期位置にそのまま位置することになる。