Vous développez un jeu de simulation où deux factions s'affrontent sur une carte en grille bidimensionnelle de taille $H \times W$.

Chaque case de la grille peut être représentée par une paire de coordonnées $(y, x)$. Les cases de la première ligne sont représentées par $(0,0), (0,1), \dots, (0, W-1)$ en partant de la gauche, et celles de la deuxième ligne par $(1,0), (1,1), \dots, (1, W-1)$. Toutes les cases jusqu'à la $H$-ième ligne sont représentées de la même manière. Les cases situées au-dessus, en dessous, à gauche et à droite d'une case donnée sont dites « adjacentes » à cette case.

La carte est composée de divers terrains, chacun ayant un niveau de « rugosité » défini. De plus, plusieurs unités sont placées sur la carte sans se chevaucher, et chaque unité appartient à l'une des deux factions en conflit. Tant qu'elle ne sort pas de la carte, chaque unité peut se déplacer vers une case adjacente depuis sa position actuelle. Le déplacement consomme une quantité de stamina égale à la rugosité du terrain de la case cible. Certains terrains sont trop accidentés pour être traversés. Si deux unités de factions différentes sont adjacentes, elles sont en état de combat.

Toutes les unités possèdent une stamina infinie car elles sont bien approvisionnées en rations de combat. Cependant, chaque unité a une limite sur la quantité totale de stamina qu'elle peut consommer en une seule « avancée rapide », ce que l'on appelle la « mobilité » de l'unité. Une avancée rapide est une action tactique où une unité en combat se déplace rapidement vers une destination relativement proche en passant par une ou plusieurs cases. Une avancée rapide n'est possible que s'il n'y a pas d'autre unité à la destination. Si une unité rencontre une unité de la même faction pendant son avancée, elle peut la traverser, mais si elle rencontre une unité d'une faction différente, un combat s'engage dès l'instant où elle devient adjacente à cette unité, elle doit donc s'arrêter à cet endroit. Cependant, si l'unité sélectionnée était déjà en état de combat, elle peut effectuer une avancée rapide pour sortir du combat.

Vous avez créé un bot qui sélectionne automatiquement des unités au hasard et leur donne des ordres d'avancée rapide pour tester la présence de bugs dans le jeu. Ce bot peut parfois donner des ordres d'avancée rapide impossibles à exécuter. Un ordre est impossible à exécuter si une autre unité se trouve à la destination, si la destination est un terrain infranchissable, ou s'il n'existe aucun chemin vers la destination en raison de la limite de mobilité. S'il n'y a pas de bug dans le jeu, ces ordres doivent être ignorés.

Il est maintenant temps de vérifier s'il y a des bugs. Écrivez un programme qui, étant donné une séquence d'ordres donnés par le bot dans l'ordre chronologique, affiche les coordonnées de chaque unité après le traitement séquentiel de tous les ordres.

Entrée

La première ligne contient le nombre de types de terrain $N$, la hauteur de la carte $H$ et la largeur de la carte $W$, séparés par des espaces. ($1 \le N \le 9$, $2 \le H, W \le 500$)

Les $H$ lignes suivantes contiennent $W$ entiers séparés par des espaces, représentant le numéro du type de terrain de chaque case de gauche à droite, chaque nombre étant compris entre $1$ et $N$.

La ligne suivante contient $N$ entiers $r_1, r_2, \dots, r_N$ ($-1 \le r_i \le 4, r_i \neq 0$) séparés par des espaces. Si $r_i$ est $-1$, cela signifie que le $i$-ième type de terrain est trop accidenté pour être pénétré ; sinon, $r_i$ représente la rugosité du $i$-ième type de terrain.

La ligne suivante contient le nombre d'unités $M$. ($1 \le M \le H \times W / 4$)

Les $M$ lignes suivantes contiennent quatre entiers $m, t, a, b$ séparés par des espaces, représentant respectivement la mobilité, la faction, la coordonnée $y$ et la coordonnée $x$ de chaque unité, de la 1ère à la $M$-ième unité. ($1 \le m \le 20$, $0 \le t \le 1$, $0 \le a < H$, $0 \le b < W$)

Chaque case contient au plus une unité, et aucune unité n'est placée sur une case de terrain infranchissable.

La ligne suivante contient le nombre d'ordres d'avancée rapide $K$ ($1 \le K \le 10\,000$).

Les $K$ lignes suivantes contiennent trois entiers $u, a, b$ séparés par des espaces, représentant un ordre d'avancée rapide pour l'unité $u$ vers $(a, b)$. ($1 \le u \le M$, $0 \le a < H$, $0 \le b < W$)

Sortie

Affichez la position des unités après le traitement de tous les ordres d'avancée rapide sur $M$ lignes. Si l'unité $i$ se trouve en $(a_i, b_i)$, affichez les deux entiers $a_i$ et $b_i$ séparés par un espace sur la $i$-ième ligne.

Exemples

Entrée 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

Sortie 1

4 3
3 3

Remarque

Pour le premier ordre d'avancée rapide, si l'on ne tient pas compte des unités de la faction adverse, il est possible d'atteindre la destination via le chemin $(2,0) \to (2,1) \to (2,2) \to (2,3) \to (1,3)$. Cependant, en raison de l'unité de la faction adverse située en $(3,3)$, un combat se produit en $(2,3)$, donc $(1,3)$ ne peut être atteint, et comme il n'existe aucun chemin de contournement permettant d'éviter le combat, la destination ne peut pas être atteinte. Par conséquent, cet ordre est impossible à exécuter et est ignoré.

Le deuxième ordre d'avancée rapide est ignoré car la position cible est un terrain infranchissable.

Le troisième ordre d'avancée rapide peut être exécuté en suivant le chemin $(2,0) \to (3,0) \to (4,0) \to (4,1) \to (4,2) \to (4,3)$, ce qui consomme 7 de stamina. Comme cette valeur n'est pas supérieure à la mobilité de l'unité, l'ordre est exécutable.

Ainsi, après le traitement de tous les ordres, l'unité 1 se trouve en $(4,3)$ suite au dernier ordre, et l'unité 2 reste à sa position initiale.