Haunted Graveyard |
The graveyard is organized as a grid of W x 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 the moment 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:
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:
The next line contains an integer E (E 0), the number of ``haunted holes'', and is followed by E lines. Each of these contains five integers X1, Y1, X2, Y2, T. (X1, Y1) is the position of the ``haunted hole'' ( 0 X1 < W and 0 Y1 < H). (X2, Y2) is the destination of the ``haunted hole'' ( 0 X2 < W and 0 Y2 < H). Note that the origin and the destination of a ``haunted hole'' can be identical. T ( -10 000 T 10 000) is the difference in seconds between the moment somebody enters the ``haunted hole'' and the moment he appears in the destination position; a positive number indicates that he reaches the destination after entering the hole. You can safely assume that there are no two ``haunted holes'' with the same origin, and the destination cell of a ``haunted hole'' does not contain a gravestone. Furthermore, there are neither gravestones nor ``haunted holes'' at positions (0,0) and (W - 1, H - 1).
The input will finish with a line containing `0 0', which should not be processed.
3 3 2 2 1 1 2 0 4 3 2 2 1 3 1 1 3 0 2 2 0 4 2 0 1 2 0 1 0 -3 0 0
Impossible 4 Never