Tonight is Halloween and Scared John and his friends have decided to do something fun to celebrate the occasion: crossing the graveyard. Although Scared John does not find this fun at all, he finally agreed to join them in their adventure. Once at the entrance, the friends have begun to cross the graveyard one by one, and now it is the time for Scared John. He still remembers the tales his grandmother told him when he was a child. She told him that, on Halloween night, "haunted holes" appear in the graveyard. These are not usual holes, but they transport people who fall inside to some point in the graveyard, possibly far away. But the scariest feature of these holes is that they allow one to travel in time as well as in space; i.e., if you fall inside a "haunted hole", you appear somewhere in the graveyard a certain time before (or after) you entered the hole, in a parallel universe otherwise identical to ours.
The graveyard is organized as a grid of W*H cells, with the entrance in the cell at position (0, 0) and the exit at (W-1, H-1). Despite the darkness, Scared John can always recognize the exit, and he will leave as soon as he reaches it, determined never to set foot anywhere in the graveyard again. On his way to the exit, he can walk from one cell to an adjacent one, and he can only head to the North, East, South or West. In each cell there can be either one gravestone, one "haunted hole", or grass:
If the cell contains a gravestone, you cannot walk over it, because gravestones are too high to climb.
If the cell contains a "haunted hole" and you walk over it, you will appear somewhere in the graveyard at a possibly different moment in time. The time difference depends on the particular "haunted hole" you fell into, and can be positive, negative or zero.
Otherwise, the cell has only grass, and you can walk freely over it.
He is terrified, so he wants to cross the graveyard as quickly as possible. And that is the reason why he has phoned you, a renowned programmer. He wants you to write a program that, given the description of the graveyard, computes the minimum time needed to go from the entrance to the exit. Scared John accepts using "haunted holes" if they permit him to cross the graveyard quicker, but he is frightened to death of the possibility of getting lost and being able to travel back in time indefinitely using the holes, so your program must report these situations.
Figure 3 illustrates a possible graveyard (the second test case from the sample input). In this case there are two gravestones in cells (2, 1) and (3, 1), and a "haunted hole" from cell (3, 0) to cell (2, 2) with a difference in time of 0 seconds. The minimum time to cross the graveyard is 4 seconds, corresponding to the path:
If you do not use the "haunted hole", you need at least 5 seconds.