Tworzysz symulację gry, w której dwie frakcje toczą bitwę na dwuwymiarowej mapie o wymiarach $H \times W$.

Każde pole na siatce można opisać parą współrzędnych $(y, x)$. Pola w pierwszym wierszu są reprezentowane od lewej strony jako $(0,0), (0,1), \dots, (0, W-1)$, a pola w drugim wierszu jako $(1,0), (1,1), \dots, (1, W-1)$. W ten sam sposób oznacza się wszystkie pola aż do wiersza $H$. Pola znajdujące się powyżej, poniżej, po lewej i po prawej stronie danego pola nazywamy polami „sąsiadującymi”.

Mapa składa się z różnych rodzajów terenu, a każdy z nich ma określony współczynnik „trudności”. Na mapie rozmieszczonych jest wiele jednostek, które nie nakładają się na siebie, a każda z nich należy do jednej z dwóch walczących frakcji. Każda jednostka może przemieszczać się na sąsiadujące pola, o ile nie opuszcza mapy. Ruch zużywa ilość staminy równą trudności terenu danego pola. Niektóre tereny są zbyt trudne, aby można było przez nie przejść. Jeśli dwie jednostki z przeciwnych frakcji znajdują się na sąsiadujących polach, są one w stanie walki.

Wszystkie jednostki posiadają nieskończoną ilość staminy, ponieważ są dobrze zaopatrzone w racje żywnościowe. Jednak każda jednostka ma ograniczoną całkowitą ilość staminy, którą może zużyć podczas jednego „zrywu”. Jest to tzw. „siła ruchu” jednostki. Zryw to manewr taktyczny, w którym jednostka szybko przemieszcza się do stosunkowo bliskiego celu, przechodząc przez jedno lub więcej pól. Zryw jest możliwy tylko wtedy, gdy na polu docelowym nie ma innej jednostki. Jeśli podczas zrywu jednostka napotka jednostkę tej samej frakcji, może przez nią przejść, ale jeśli napotka jednostkę wrogiej frakcji, musi zatrzymać się w miejscu, w którym staje się z nią sąsiadująca, ponieważ w tym momencie rozpoczyna się walka. Jeśli jednak wybrana jednostka była już w stanie walki, może wykonać zryw, aby się z niej wycofać.

Stworzyłeś bota, który automatycznie wybiera losowe jednostki i wydaje im rozkazy zrywu, aby przetestować grę pod kątem błędów. Bot może wydawać rozkazy, których nie da się wykonać. Rozkaz jest niewykonalny, jeśli na polu docelowym znajduje się inna jednostka, pole docelowe jest nieprzejezdne lub jeśli ze względu na limit siły ruchu nie istnieje ścieżka do celu. Jeśli w grze nie ma błędów, takie rozkazy powinny być ignorowane.

Napisz program, który po otrzymaniu chronologicznej listy rozkazów wydanych przez bota, wypisze współrzędne każdej jednostki po wykonaniu wszystkich poleceń.

Wejście

W pierwszej linii podano liczbę rodzajów terenu $N$, wysokość mapy $H$ oraz szerokość mapy $W$ oddzielone spacjami ($1 \le N \le 9$, $2 \le H, W \le 500$).

Następnie w $H$ liniach podano po $W$ liczb całkowitych oznaczających numer terenu każdego pola, przy czym każda liczba mieści się w zakresie od $1$ do $N$.

W kolejnej linii podano $N$ liczb całkowitych $r_1, r_2, \dots, r_N$ ($-1 \le r_i \le 4, r_i \neq 0$) oddzielonych spacjami. Jeśli $r_i$ wynosi $-1$, oznacza to, że $i$-ty teren jest zbyt trudny i nie można na niego wejść; w przeciwnym razie $r_i$ oznacza trudność $i$-tego terenu.

W kolejnej linii podano liczbę jednostek $M$ ($1 \le M \le H \times W / 4$).

Następnie w $M$ liniach podano cztery liczby całkowite $m, t, a, b$ oznaczające odpowiednio siłę ruchu, frakcję, współrzędną $y$ oraz współrzędną $x$ jednostki ($1 \le m \le 20, 0 \le t \le 1, 0 \le a < H, 0 \le b < W$).

Na każdym polu znajduje się maksymalnie jedna jednostka, a na polach nieprzejezdnych nie ma żadnych jednostek.

W kolejnej linii podano liczbę rozkazów zrywu $K$ ($1 \le K \le 10\,000$).

Następnie w $K$ liniach podano trzy liczby całkowite $u, a, b$ oznaczające rozkaz zrywu jednostki $u$ do pola $(a, b)$ ($1 \le u \le M, 0 \le a < H, 0 \le b < W$).

Wyjście

W $M$ liniach wypisz pozycje jednostek po przetworzeniu wszystkich rozkazów zrywu. Jeśli jednostka $i$ znajduje się na pozycji $(a_i, b_i)$, wypisz dwie liczby całkowite $a_i, b_i$ oddzielone spacją.

Przykład

Wejście 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

Wyjście 1

4 3
3 3

Uwagi

W przypadku pierwszego rozkazu zrywu, gdyby nie brać pod uwagę jednostek wrogiej frakcji, można by dotrzeć do celu ścieżką $(2,0) \to (2,1) \to (2,2) \to (2,3) \to (1,3)$. Jednak z powodu wrogiej jednostki znajdującej się na $(3,3)$, w $(2,3)$ dochodzi do walki, więc nie można dotrzeć do $(1,3)$. Ponieważ nie ma innej ścieżki, która pozwoliłaby ominąć walkę, dotarcie do celu jest niemożliwe. W związku z tym rozkaz jest niewykonalny i zostaje zignorowany.

Drugi rozkaz zrywu jest niewykonalny, ponieważ pole docelowe jest nieprzejezdne, więc zostaje zignorowany.

Trzeci rozkaz zrywu można wykonać, poruszając się ścieżką $(2,0) \to (3,0) \to (4,0) \to (4,1) \to (4,2) \to (4,3)$, co zużywa 7 jednostek staminy. Jest to wartość nieprzekraczająca siły ruchu jednostki, więc rozkaz jest wykonalny.

W rezultacie, po przetworzeniu wszystkich rozkazów, jednostka nr 1 znajduje się na pozycji $(4,3)$ zgodnie z ostatnim rozkazem, a jednostka nr 2 pozostaje na swojej pozycji początkowej.