Minimum Stamp Operations to Create a White Path

President K loves solving mazes. He has an \( R \times C \) grid where each cell is either white or black. The cell in the \( i \)-th row and \( j \)-th column is denoted as Cell \( (i, j) \).

The president fixed a starting cell \( (S_r, S_c) \) and a goal cell \( (G_r, G_c) \). He can only travel through white cells in the four cardinal directions (up, down, left, right). However, the grid might be arranged so that no white path exists between the start and the goal.

To solve his maze, he employs a stamp of size \( N \times N \). In one Operation, he selects integers \( a, b \) satisfying \( 1 \leq a \leq R - N + 1 \) and \( 1 \leq b \leq C - N + 1 \) and paints every cell in the square region \[ [a, a+N-1] \times [b, b+N-1] \] white.

Your task is to compute the minimum number of operations needed to guarantee that there is a path from the starting cell to the goal cell consisting solely of white cells.

inputFormat

The first line contains three integers ( R ), ( C ), and ( N ) representing the number of rows, the number of columns, and the stamp size respectively (with ( 1 \leq R, C \leq 10 )).

The second line contains four integers ( S_r ), ( S_c ), ( G_r ), and ( G_c ) specifying the starting cell and the goal cell ((1 \leq S_r, S_c, G_r, G_c \leq R, C)).

The following ( R ) lines each contain a string of length ( C ), consisting of characters '.' (white cell) and '#' (black cell).

outputFormat

Output a single integer: the minimum number of operations required such that there exists a path from the starting cell to the goal cell that uses only white cells.

sample

3 3 1
1 1 3 3
..#
###
#..

2