Kangaroo Commotion

Bushfires are threatening your habitat. As a kangaroo, you must warn the other kangaroos in your troop as fast as possible and flee to a safe area.

You stand still at the start and jump to the other kangaroos' locations. You visit them in a specific order so that each one has enough time to escape. After visiting all of them, you keep jumping to the safe area and stop there.

Each jump moves you a possibly negative integer distance north and/or east. Your muscles are limited, so you can change your speed in each direction by at most $1$ per jump. Formally, if jump $i$ moves you $v_{x,i}$ north and $v_{y,i}$ east, then jump $i+1$ must satisfy $|v_{x,i+1} - v_{x,i}| \leq 1$ and $|v_{y,i+1} - v_{y,i}| \leq 1$.

Find the minimal number of jumps needed to go from your current position to the safe area via all other kangaroos, without leaving the grid. You must come to a full stop at the end, so the last jump must both start and end at the safe area.

Figure K.1 shows one possible way to reach the safe area in 9 jumps in Sample 1.

The first line contains three integers $r$, $c$ ($1\leq r, c \leq 50$), the number of rows and columns of the grid, and $k$ ($1\leq k\leq 5$), the number of other kangaroos you need to warn.

The next $r$ lines each contain $c$ characters. A . is an open space and a # is a bush where you cannot jump. Your start position is 0. The characters 1 to k mark the other kangaroos, in this order. The character k+1 marks the safe area where you should stop.

If you can reach the safe area, output the minimal number of jumps needed. Otherwise, output impossible.