你正在開發一款模擬遊戲，在 $H \times W$ 的二維網格地圖上，兩個勢力正在進行戰鬥。

網格中的每個格子可以用 $y$ 座標與 $x$ 座標的數對 $(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 號單位開始，每個單位的移動力、勢力、所在格子的 $y$ 座標、所在格子的 $x$ 座標，共四個整數 $m, t, a, b$，以空格分隔。($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)$，則輸出 $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 號單位維持在初始位置。