전투 시뮬레이션

당신은 $H \times W$ 크기의 2차원 격자 맵에서 두 세력이 전투를 벌이는 시뮬레이션 게임을 개발하고 있다. 격자의 각 칸은 $y$좌표와 $x$좌표의 쌍 $(y, x)$로 표현할 수 있다. 첫 번째 줄의 칸들은 왼쪽부터 $(0, 0), (0, 1), \cdots, (0, W-1)$로 표현하고, 두 번째 줄의 칸들은 $(1, 0), (1, 1), \cdots, (1, W-1)$로 표현한다. 같은 방식으로 마지막 줄까지 모든 칸을 좌표로 표현한다. 어떤 칸의 위, 아래, 왼쪽, 오른쪽 칸은 그 칸에 인접한 칸이라고 한다.

맵은 여러 지형으로 이루어져 있고, 각 지형은 정해진 험준도 수치를 가진다. 맵에는 여러 유닛이 서로 겹치지 않게 배치되어 있으며, 각 유닛은 두 세력 중 한 세력에 속한다. 각 유닛은 맵 밖으로 벗어나지 않는 한 지금 있는 칸에서 상하좌우로 인접한 칸으로 이동할 수 있다. 이동할 때마다 들어간 칸 지형의 험준도만큼 스태미나를 소모한다. 일부 지형은 너무 험준하여 진입할 수 없다. 세력이 다른 두 유닛이 인접해 있으면 두 유닛은 교전 상태이다.

모든 유닛은 전투식량을 든든히 챙겨 나왔기 때문에 스태미나가 무한하다. 다만 각 유닛은 한 번의 약진에서 소모할 수 있는 스태미나 총량이 제한되어 있으며, 이 한도를 유닛의 이동력이라고 한다. 약진은 전투 중인 유닛이 비교적 가까운 목표 지점까지 단숨에 달려가는 전술 행동으로, 하나 이상의 칸을 거쳐 이동하는 것이다. 약진은 목표 지점에 다른 유닛이 없어야만 가능하다. 약진 중 같은 세력의 유닛을 만나면 통과할 수 있지만, 다른 세력의 유닛을 만나 그 유닛과 상하좌우로 인접하게 되면 교전이 벌어지므로 그 자리에서 멈춰야 한다. 다만 선택된 유닛이 이미 교전 상태였다면 약진하여 교전에서 벗어날 수 있다.

봇이 임의의 유닛을 골라 약진 명령을 내리며 게임에 버그가 있는지 테스트하고 있다. 이 봇은 수행할 수 없는 약진 명령도 내린다. 목표 지점에 다른 유닛이 있거나, 목표 지점이 이동할 수 없는 지형이거나, 이동력의 한계 때문에 목표 지점에 도달하는 경로가 없으면 그 명령은 수행할 수 없다. 게임에 버그가 없다면 이런 명령은 무시되어야 한다.

이제 버그가 있는지 확인할 차례이다. 봇이 내린 명령들이 시간 순으로 주어졌을 때, 모든 명령을 순서대로 처리한 뒤 각 유닛의 좌표를 출력하는 프로그램을 작성하시오.

첫 줄에 지형의 종류 수 $N$, 맵의 세로 길이 $H$, 맵의 가로 길이 $W$가 공백으로 구분되어 주어진다. ($1 \leq N \leq 9$, $2 \leq H,W \leq 500$)

이어서 $H$개의 줄에 걸쳐 왼쪽부터 차례대로 각 칸의 지형 번호를 나타내는 $W$개의 정수가 공백으로 구분되어 주어진다. 각 수는 $1$ 이상 $N$ 이하이다.

다음 줄에 $N$개의 정수 $r_1, r_2, \cdots, r_N$ ($-1 \leq r_i \leq 4$, $r_i \neq 0$)이 공백으로 구분되어 주어진다. $r_i$가 $-1$이면 $i$번 지형이 너무 험준하여 진입할 수 없음을 뜻하며, 그 외의 경우 $r_i$는 $i$번 지형의 험준도이다.

다음 줄에 유닛의 수 $M$이 주어진다. ($1 \leq M \leq H \times W / 4$)

이어서 $M$개의 줄에 걸쳐 1번 유닛부터 차례로 이동력 $m$, 세력 $t$, 유닛이 있는 칸의 $y$좌표 $a$, $x$좌표 $b$가 공백으로 구분되어 주어진다. ($1 \leq m \leq 20$, $0 \leq t \leq 1$, $0 \leq a < H$, $0 \leq b < W$)

각 칸에는 최대 하나의 유닛이 배치되며, 진입할 수 없는 지형의 칸에는 유닛이 배치되지 않는다.

다음 줄에 약진 명령의 개수 $K$가 주어진다. ($1 \leq K \leq 10\ 000$)

이어서 $K$개의 줄에 걸쳐 약진 명령을 나타내는 세 정수 $u$, $a$, $b$가 공백으로 구분되어 주어진다. ($1 \leq u \leq M$, $0 \leq a < H$, $0 \leq b < W$) 이는 $u$번 유닛을 $(a, b)$로 약진시키는 명령이다.

$M$개의 줄에 걸쳐 모든 약진 명령을 처리한 후의 유닛 위치를 출력한다. $i$번 유닛이 $(a_i, b_i)$에 위치하면 $i$번째 줄에 두 정수 $a_i$, $b_i$를 공백으로 구분하여 출력한다.

첫 번째 약진 명령은 수행할 수 없다. 적대 세력을 고려하지 않으면 $(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번 유닛은 초기 위치에 그대로 있다.