잔켄 택틱스

잔켄(가위바위보로도 알려진)은 널리 사랑받는 어린이 놀이입니다. 게임 개발의 오랜 전통에 따라, 한 회사가 이 고전에 전략적 변주를 더하기로 했습니다. 그 결과물인 전쟁 시뮬레이션 Janken Tactics가 개발 중이며, 여러분은 프로그래머로 합류해 이동 판정(move validation) 코드를 맡게 되었습니다.

Janken Tactics는 각 변에 다섯 칸이 있는 육각-육각(hex-hex) 격자 위에서 진행됩니다. 각 칸에는 이동을 돕거나 방해하는 지형이 있습니다. 인접한 칸으로 이동하는 기본 비용은 이동력 1이지만, 도착 칸의 지형에 따라 더 들 수 있습니다.

평지(Field)로 이동: 추가 비용 없음 (총 1)
숲(Woods)으로 이동: 추가 1 (총 2)
언덕(Hills)으로 이동: 추가 2 (총 3)
산(Mountains)으로 이동: 추가 3 (총 4)
물속(Underwater) 칸으로는 어떤 유닛도 이동할 수 없습니다. (유닛은 물속 칸에서 시작하지도 않습니다.)

격자의 배치와 좌표계는 다음과 같습니다.

      4 5 6 7 8 9
     3 \ \ \ \ \ \
    2 \ \ * * * * * -- A
   1 \ \ * * * * * * -- B
    \ \ * * * * * * * -- C
     \ * * * * * * * * -- D
      * * * * * * * * * -- E
       * * * * * * * * -- F
        * * * * * * * -- G
         * * * * * * -- H
          * * * * * -- I

칸의 좌표는 행 문자(A-I) 뒤에 열 번호를 붙여 표기합니다. 맨 윗 행의 가운데 칸은 A7이고, 격자의 가장 오른쪽 꼭짓점은 E9입니다. 인접한 칸은 같은 행에서 바로 왼쪽·오른쪽 두 칸과 대각선 방향의 네 칸입니다. 예를 들어 E5에 인접한 칸은 D5, D6, E4, E6, F4, F5입니다.

잔켄처럼 유닛은 세 종류입니다: 가디언(Guardian, 바위), 메이지(Mage, 보), 소드맨(Swordsman, 가위). 모든 유닛은 한 번의 이동에 쓸 수 있는 이동력 10을 가집니다. 상성은 다음과 같습니다.

가디언은 소드맨을 이기지만 메이지에게 집니다.
메이지는 가디언을 이기지만 소드맨에게 집니다.
소드맨은 메이지를 이기지만 가디언에게 집니다.

여러분이 만드는 것은 전투 코드가 아니지만, 이 상성은 이동에서도 중요합니다. 이동 도중 유닛은 적 유닛 위를 지나갈 수 없고, 자신을 이기는(상성상 강한) 적 유닛의 한 칸 이내로도 지나갈 수 없습니다(가디언은 메이지의 한 칸 이내로, 메이지는 소드맨의 한 칸 이내로, 소드맨은 가디언의 한 칸 이내로 지나갈 수 없습니다). 다만 이동을 끝내는 칸은 (같은 칸이 아니라면) 어떤 적 유닛과도 인접할 수 있으며, 아군 유닛이 있는 칸은 종류에 관계없이 통과할 수 있습니다. 도착 칸은 아군이든 적군이든 비어 있어야 합니다. 이동과 이동 사이에 한 칸에 유닛이 둘 이상 있는 경우는 없습니다.

여러분의 과제는 주어진 유닛이 요청한 이동을 할 수 있는지, 할 수 있다면 이동 후 남는 이동력이 얼마인지 판정하는 것입니다. 남는 이동력이 최대가 되는 경로를 선택하세요. 다음 경우 이동은 무효입니다.

출발 칸에 유닛이 없다.
도착 칸이 이미 점유되어 있다.
도착 칸에 닿는 비용이 유닛의 이동력보다 크다.
물속 칸이나 적 유닛 위를 지나거나, 자신을 이기는 적 유닛 옆을 지나지 않고서는 도착 칸에 닿을 수 없다.

여러분은 여러 이동을 차례로 처리합니다. 이동이 무효이면 그 유닛(있다면)은 출발 칸에 그대로 남습니다. 한 데이터 세트의 이동들은 순서대로 일어나며, 이동마다 격자를 초기 상태로 되돌리지 않습니다.

입력의 첫 줄에는 데이터 세트의 개수 $n$이 주어집니다. 각 데이터 세트는 다음과 같이 구성됩니다.

먼저 격자의 지형을 나타내는 아홉 줄이 A행부터 I행까지 한 줄씩 주어집니다. 각 지형은 F(평지), W(숲), H(언덕), M(산), U(물속)로 표기하며, 각 줄의 칸은 열 번호가 커지는 순서(왼쪽에서 오른쪽)로 나열됩니다.

다음 줄에는 두 정수 $M$ $P$ ($1 \le M, P \le 10$), 즉 양편의 유닛 수가 주어집니다. 이어지는 $M$개의 줄에는 각각 유닛 종류 $T$와 위치 $L$이 주어지는데, $T$는 G(가디언), M(메이지), S(소드맨) 중 하나이고 $L$은 위 좌표 형식의 시작 칸입니다. 그다음 $P$개의 줄은 같은 형식으로 상대편을 나타냅니다.

다음 줄에는 시험할 이동의 수 $V$ ($1 \le V \le 100$)가 주어집니다. 이어지는 $V$개의 줄에는 각각 두 좌표 $S$ $E$가 주어지며, $S$는 출발 칸(따라서 이동할 유닛), $E$는 시도하는 도착 칸입니다. 이동은 어느 편의 것이든 될 수 있습니다.

잔켄 택틱스

문제

입력

출력