게임

할(Hal)과 데이브(Dave)가 R행 C열짜리 직사각형 판 위에서 게임을 한다. 규칙은 다음과 같다.

• 판 위에는 말이 하나 있고, 두 사람이 번갈아 가며 이 말을 움직인다.
• 한 번의 이동은 말을 아래, 오른쪽, 오른쪽 아래 대각선 세 방향 중 하나로 인접한 칸으로 옮기는 것이다.
• 일부 칸은 금지된 칸이며, 말은 절대 그 칸으로 들어갈 수 없다.
• 각 칸에는 음식이 최대 하나 놓여 있다. 말을 햄버거 칸으로 옮긴 사람은 1점, 감자튀김 칸으로 옮긴 사람은 3점, 아이스크림 칸으로 옮긴 사람은 5점을 얻는다.
• 자기 차례인 사람이 어떤 이동도 할 수 없을 때(세 방향이 모두 판 밖으로 나가거나 금지된 칸으로 들어가게 될 때) 게임이 끝난다.
• 게임이 끝났을 때 두 사람의 점수가 같으면, 이동할 수 없는 사람이 진다. 점수가 다르면 점수가 더 높은 사람이 이긴다.
• 두 사람 모두 0점에서 시작하며 할이 먼저 움직인다. 말의 시작 칸은 금지된 칸이 아니고 음식도 없는 칸이다.

어떤 게임이든 유한한 횟수의 이동 뒤에 반드시 끝나므로, 시작 칸이 정해지면 두 사람 중 정확히 한 명이 상대가 어떻게 두더라도 이길 수 있는 필승 전략을 가진다.

판, 금지된 칸, 음식 칸, 그리고 여러 개의 시작 위치가 주어진다. 각 시작 위치에 대해 어느 쪽이 필승 전략을 가지는지 구하여라.

첫째 줄에 판의 행 수 R과 열 수 C가 공백으로 구분되어 주어진다 (2 ≤ R ≤ 100, 2 ≤ C ≤ 100).

다음 R개의 줄에는 각각 판의 한 행을 나타내는 C개의 문자가 주어진다.

• # — 금지된 칸
• H — 햄버거, F — 감자튀김, I — 아이스크림
• . — 음식이 없는 보통 칸

그다음 줄에는 판정할 시작 위치의 개수 N이 주어진다 (1 ≤ N ≤ 100).

이어지는 N개의 줄에는 각각 시작 위치의 행 A와 열 B가 공백으로 구분되어 주어진다 (1 ≤ A ≤ R, 1 ≤ B ≤ C). 행은 위에서 아래로 1부터 R까지, 열은 왼쪽에서 오른쪽으로 1부터 C까지 번호가 매겨진다.

N개의 줄을 출력한다. i번째 줄에는 i번째 시작 위치에 대해 필승 전략을 가진 사람의 이름 HAL 또는 DAVE를 출력한다.