Game

Hal and Dave play a game on a rectangular board with R rows and C columns. The rules are:

• A single piece sits on the board, and the two players move it alternately.
• One move slides the piece to an adjacent square in one of three directions: down, right, or diagonally down-right.
• Some squares are forbidden; the piece may never enter them.
• Each square holds at most one food item. A player who moves the piece onto a hamburger scores 1 point, onto french fries 3 points, and onto ice cream 5 points.
• The game ends when the player whose turn it is has no legal move, meaning all three directions would leave the board or enter a forbidden square.
• If both players finish with the same score, the player who cannot move loses. If the scores differ, the player with the higher score wins.
• Both players start with 0 points and Hal moves first. The piece begins on a square that is not forbidden and holds no food.

Because every game ends after finitely many moves, for any starting square exactly one player has a winning strategy, a way to win no matter how the opponent plays.

You are given the board, the forbidden squares, the food squares, and several starting positions. For each starting position, determine which player has a winning strategy.

The first line contains two integers R and C (2 ≤ R ≤ 100, 2 ≤ C ≤ 100), the number of rows and columns, separated by a space.

Each of the next R lines contains C characters describing one row of the board:

• # — a forbidden square
• H — a hamburger, F — french fries, I — ice cream
• . — an ordinary empty square

The next line contains an integer N (1 ≤ N ≤ 100), the number of starting positions to evaluate.

Each of the following N lines contains two integers A and B (1 ≤ A ≤ R, 1 ≤ B ≤ C), the row and column of a starting position. Rows are numbered 1 to R from top to bottom, and columns 1 to C from left to right.

Print N lines. The i-th line contains the name of the player who has a winning strategy for the i-th starting position: HAL or DAVE.