Jumping King Jelly (Small)

Interview

Time limit1sMemory limit128 MB

Summary
Given an N by N board with jump numbers, move only right or down from the top-left and reach the bottom-right, or report failure.
Level

Medium5 of 10

Topics
DFS, Backtracking, Brute force, Array
Solved
No attempts yet

Problem

Jelly is a jelly that loves to jump. Tired of simply jumping, Jelly wants to try a new jumping game. The rules of the new jumping game are as follows.

  1. Jelly can move only inside a square region whose width and height have the same number of cells. If Jelly leaves the square region, it falls to the floor and immediately loses the game.
  2. Jelly always starts at the top-left cell of the square. It never starts from any other cell.
  3. Jelly can move only to the right and downward. It cannot move upward or to the left.
  4. The moment Jelly reaches the bottom-right cell, the game ends immediately with Jelly's victory.
  5. The number of cells Jelly can move in one jump equals the number written on the cell it is currently standing on. It cannot move more or fewer cells than that number.

Jelly liked the new game, kept playing, and finally reached the last stage. However, the region where the game is played has become so large that Jelly can no longer tell whether the game can be won. Jelly asked you, a capable programmer, to find out whether the given region can be won. Help Jelly determine whether it can reach the end point (the bottom-right cell) in the given game region!

Input

The first line of the input gives the size of the game region NN (2≤N≤32 \le N \le 3).

From the second line to the last line, the game board region (map) is given.

The victory point of the board (the bottom-right cell) contains -1, and every other cell contains an integer from 0 to 100.

Output

Print “HaruHaru” (without quotation marks) on one line if Jelly can reach the end point, or “Hing” (without quotation marks) if it cannot.

Examples2

  1. Example 1

    Input
    3
    1 1 10
    1 5 1
    2 2 -1
    
    Expected output
    HaruHaru
    
  2. Example 2

    Input
    3
    2 2 1
    2 2 2
    1 2 -1
    
    Expected output
    Hing