21992_WalkingtheLabyrin

Your friend is developing scenarios for quest-type computer games and often turns to you to ask about the correctness of his ideas. He has done it again just now.

The labyrinth is a grid of square cells. The cells are arranged in M lines from North to South and N columns from West to East. The coordinates of the North-Western cell of the grid are (1, 1); the coordinates of the South-Eastern cell are (N, M). From the outside, the labyrinth is surrounded by non-passable external wall. Inside the labyrinth, any cell can be either empty or contain a section of an internal wall. Among the empty cells, K are prepared for laying mines. When a mine explodes in one of those cells, it destroys the internal walls in the horizontally and vertically neighboring cells, making the cells empty.

The player's character enters the labyrinth through some empty cell A and has to exit it through an empty cell B, distinct from the cell A. He can move only though empty cells, stepping from a cell to a neighboring one horizontally or vertically. Stepping from a cell to its neighbor is a move.

The character has one mine that he can (but does not have to) explode it in one of the prepared cells. To do this, the character has to enter the cell, plant the mine, move outside the explosion zone, and then remotely explode the mine. If the mine is planted in the cell (x₀, y₀), then any cell (x₁, y₁) is outside the explosion zone if at least one of the following holds:

• |x₁ - x₀| + |y₁ - y₀| ≥ 5;

• the straight segment connecting the centers of the two cells has at least one common point with an internal wall not destroyed in the explosion.

According to the rules of the game, after the explosion, the player has to return to the cell where he planted the mine.

On the figure below, if the mine explodes in the cell marked with 1, the cells marked with 2 are safe (and the player can get there to hide in during the explosion). The cells with surviving internal walls have gray background; the cells with destroyed internal walls have black background.

Your task is to find the shortest (with the minimal number of moves) route from the cell A to the cell B.

Note that the count must also include any moves needed to get to a safe cell before and to return to the location of the mine after the explosion, but planting the mine and exploding it are not counted as moves!

The input consists of several lines. The first line contains the integers M, N, K (1 ≤ M, N ≤ 100, M*N > 1, 0 ≤ K ≤ 10). The second and third lines contain the coordinates of the cells A and B. Each of the following M lines contains exactly N characters, describing the labyrinth in the order from North to South. A star (*) denotes a cell filled with an internal wall, a point (.) an empty cell, and the 'at' sign (@) a cell prepared for planting a mine.

The single line of the output should contain the minimal number of moves needed to reach the cell B. If this is impossible, output the value 0.

Sample #1
5 7 2
1 5
7 1
***.**.
@..***.
**...@*
...****
.******

Sample #2
5 7 2
1 5
7 1
***.**.
@..**..
**....*
**...**
@******

Sample #1
18

Sample #2
0

Comment case #1: The player should explode the mine in the cell (6, 3), hiding in (3, 2) or (3, 4) during the explosion.

Comment case #2: The mine can't be exploded in the cell (1, 5), as there's no safe cell to hide in during the explosion.