Safe Homecoming

Little H finds himself trapped in a rectangular grid (divided into n×m cells) representing a blockade. His goal is to return safely home. Initially, Little H starts with full health of 6 points. Every move to an adjacent cell in one of the four directions (up, down, left, right) costs him 1 HP. He cannot remain stationary. If his HP drops to 0 at any moment after moving, he dies immediately (even if he lands on a cell which normally replenishes his health).

Some cells contain a mouse. When Little H steps onto such a cell (denoted by 4), he instantly and costlessly regains full health (6 HP), provided that he is still alive upon arrival. Note that if the move causes his HP to fall to 0, even if the cell contains a mouse, he dies before he can recover.

The grid is marked with 5 types of cells:

• 0: Obstacle – cannot be passed.
• 1: Empty cell – Little H can move freely.
• 2: Starting point – also treated as an empty cell.
• 3: Home – the destination.
• 4: A special empty cell with a mouse – stepping here replenishes HP.

Your task is to determine whether Little H can safely return home without dying. If it is possible, output the minimum number of moves required. Otherwise, output ===.

Note that Little H is not allowed to leave the borders of the grid.

inputFormat

The input consists of multiple lines. The first line contains two integers n and m (the number of rows and columns of the grid). Following this, there are n lines, each line containing m space‐separated integers. Each integer is one of {0, 1, 2, 3, 4} representing:

• 0: Obstacle
• 1: Empty cell
• 2: Starting point
• 3: Home
• 4: Empty cell with a mouse (recharge cell)

outputFormat

If Little H can safely return home, output the minimum number of moves required. Otherwise, output ===.

sample

3 3
2 1 3
1 0 1
1 4 1

2