Вы разрабатываете симуляционную игру, в которой две фракции сражаются на двумерной сетке размером $H \times W$.

Каждая клетка сетки может быть представлена парой координат $(y, x)$. Клетки первой строки обозначаются как $(0,0), (0,1), \dots, (0, W-1)$ слева направо, клетки второй строки — как $(1,0), (1,1), \dots, (1, W-1)$, и так далее до $H$-й строки. Клетки, расположенные сверху, снизу, слева и справа от данной клетки, называются «соседними».

Карта состоит из различных типов местности, каждый из которых имеет определенный показатель «пересеченности». На карте размещено несколько юнитов, которые не перекрывают друг друга, и каждый юнит принадлежит к одной из двух сражающихся фракций. Юнит может перемещаться из текущей клетки в соседнюю, если она не выходит за пределы карты. При перемещении расходуется количество выносливости, равное показателю пересеченности местности клетки. Некоторые типы местности слишком пересеченные, и перемещение по ним невозможно. Если два юнита разных фракций находятся в соседних клетках, они считаются находящимися в состоянии боя.

Все юниты имеют бесконечный запас выносливости, так как они обеспечены продовольствием. Однако для каждого юнита ограничено максимальное количество выносливости, которое он может потратить за один «рывок». Рывок — это тактическое действие, при котором юнит быстро перемещается к относительно близкой целевой точке, проходя через одну или несколько клеток. Рывок возможен только в том случае, если в целевой точке нет другого юнита. Во время рывка юнит может проходить сквозь юнитов своей фракции, но если он встречает юнита другой фракции, он должен остановиться в клетке, соседней с этим юнитом, так как в этот момент начинается бой. Однако, если выбранный юнит уже находился в состоянии боя, он может совершить рывок, чтобы выйти из боя.

Вы создали бота, который автоматически выбирает случайного юнита и отдает приказ о рывке, чтобы протестировать игру на наличие ошибок. Бот может отдавать невыполнимые приказы. Приказ считается невыполнимым, если в целевой точке находится другой юнит, если целевая точка является непроходимой местностью или если путь к целевой точке не существует из-за ограничения мобильности. Если в игре нет ошибок, такие приказы должны игнорироваться.

Пришло время проверить наличие ошибок. Напишите программу, которая по списку приказов, отданных ботом в хронологическом порядке, выводит координаты каждого юнита после последовательного выполнения всех приказов.

Входные данные

В первой строке заданы количество типов местности $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$ строк, каждая из которых содержит четыре целых числа $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$, разделенных пробелами ($1 \le u \le M, 0 \le a < H, 0 \le b < W$), что означает приказ юниту $u$ совершить рывок в точку $(a, b)$.

Выходные данные

Выведите $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 остается на своей начальной позиции.