Estás desarrollando un juego de simulación donde dos facciones luchan en un mapa de cuadrícula bidimensional de tamaño $H \times W$.

Cada celda de la cuadrícula se puede representar mediante un par de coordenadas $(y, x)$. Las celdas de la primera fila se representan como $(0,0), (0,1), \dots, (0, W-1)$ de izquierda a derecha, y las de la segunda fila como $(1,0), (1,1), \dots, (1, W-1)$. De la misma manera, todas las celdas hasta la fila $H$ se representan mediante coordenadas. Las celdas arriba, abajo, a la izquierda y a la derecha de una celda dada se denominan celdas "adyacentes".

El mapa está compuesto por diversos terrenos, y cada terreno tiene un valor de "rugosidad" determinado. Además, hay varias unidades colocadas en el mapa sin solaparse, y cada unidad pertenece a una de las dos facciones en conflicto. Cada unidad puede moverse desde su ubicación actual a una celda adyacente, siempre que no salga del mapa. Al moverse, se consume una cantidad de estamina igual a la rugosidad del terreno de la celda de destino. Algunos terrenos son demasiado escarpados y el movimiento a través de ellos puede ser imposible. Si dos unidades de facciones diferentes están adyacentes, se encuentran en estado de combate.

Todas las unidades tienen estamina infinita porque llevan consigo suficientes raciones de combate. Sin embargo, cada unidad tiene un límite en la cantidad total de estamina que puede consumir en un solo "avance rápido", lo cual se denomina "capacidad de movimiento" de la unidad. Un avance rápido es una acción táctica en la que una unidad en combate se desplaza rápidamente hacia un punto objetivo relativamente cercano, atravesando una o más celdas. Un avance rápido solo es posible si no hay otra unidad en el punto objetivo. Si la unidad encuentra a otra unidad de su misma facción durante el avance, puede pasar a través de ella; sin embargo, si encuentra a una unidad de una facción diferente, el avance debe detenerse en el momento en que se vuelve adyacente a dicha unidad, ya que se produce un combate. No obstante, si la unidad seleccionada ya estaba en estado de combate, puede realizar un avance rápido para salir del combate.

Has creado un bot que selecciona automáticamente unidades al azar y les da órdenes de avance rápido para probar si hay errores en el juego. Este bot a veces emite órdenes de avance rápido imposibles de ejecutar. Una orden es imposible de ejecutar si hay otra unidad en el punto objetivo, si el punto objetivo es un terreno intransitable, o si no existe un camino hacia el punto objetivo debido al límite de la capacidad de movimiento. Si no hay errores en el juego, dichas órdenes deben ser ignoradas.

Ahora es el momento de comprobar si existen errores. Escribe un programa que, dadas las órdenes emitidas por el bot en orden cronológico, imprima las coordenadas de cada unidad después de que todas las órdenes hayan sido procesadas secuencialmente.

Entrada

La primera línea contiene el número de tipos de terreno $N$, la altura del mapa $H$ y el ancho del mapa $W$, separados por espacios. ($1 \le N \le 9$, $2 \le H, W \le 500$)

A continuación, se proporcionan $H$ líneas, cada una con $W$ números enteros separados por espacios que indican el número de tipo de terreno de cada celda de izquierda a derecha, donde cada número está entre $1$ y $N$ inclusive.

La siguiente línea contiene $N$ números enteros $r_1, r_2, \dots, r_N$ ($-1 \le r_i \le 4, r_i \neq 0$) separados por espacios. Si $r_i$ es $-1$, significa que el $i$-ésimo terreno es demasiado escarpado para entrar; de lo contrario, $r_i$ representa la rugosidad del $i$-ésimo terreno.

La siguiente línea contiene el número de unidades $M$. ($1 \le M \le H \times W / 4$)

A continuación, se proporcionan $M$ líneas, cada una con cuatro números enteros $m, t, a, b$ separados por espacios, que representan la capacidad de movimiento, la facción, la coordenada $y$ y la coordenada $x$ de la unidad, respectivamente, para cada unidad desde la número 1 en adelante. ($1 \le m \le 20, 0 \le t \le 1, 0 \le a < H, 0 \le b < W$)

Cada celda contiene como máximo una unidad, y no se colocan unidades en celdas con terrenos intransitables.

La siguiente línea contiene el número de órdenes de avance rápido $K$ ($1 \le K \le 10\,000$).

A continuación, se proporcionan $K$ líneas, cada una con tres números enteros $u, a, b$ separados por espacios, que representan una orden de avance rápido para la unidad $u$ hacia $(a, b)$. ($1 \le u \le M, 0 \le a < H, 0 \le b < W$)

Salida

Imprime la ubicación de las unidades después de que todas las órdenes de avance rápido hayan sido procesadas, a lo largo de $M$ líneas. Si la unidad $i$ se encuentra en $(a_i, b_i)$, imprime los dos números enteros $a_i$ y $b_i$ separados por un espacio en la $i$-ésima línea.

Ejemplos

Entrada 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

Salida 1

4 3
3 3

Nota

En el caso de la primera orden de avance rápido, si no se consideran las unidades de facciones enemigas, se podría llegar al objetivo siguiendo el camino $(2,0) \to (2,1) \to (2,2) \to (2,3) \to (1,3)$. Sin embargo, debido a la unidad de facción enemiga ubicada en $(3,3)$, se produce un combate en $(2,3)$, por lo que no se puede llegar a $(1,3)$, y como no hay un camino para rodear y evitar el combate, tampoco se puede llegar. Por lo tanto, esta orden es imposible de ejecutar y se ignora.

La segunda orden de avance rápido se ignora porque la ubicación objetivo es un terreno intransitable.

La tercera orden de avance rápido se puede ejecutar siguiendo el camino $(2,0) \to (3,0) \to (4,0) \to (4,1) \to (4,2) \to (4,3)$, consumiendo 7 de estamina. Como este valor no es mayor que la capacidad de movimiento de la unidad, es una orden ejecutable.

Por lo tanto, después de procesar todas las órdenes, la unidad 1 se encuentra en $(4,3)$ debido a la última orden, y la unidad 2 permanece en su posición inicial.