Running

Jinyoung wants to run in a gym of size $N \times M$ to lose weight. The gym is divided into $1 \times 1$ cells, and each cell is either empty or a wall. The cell in row $x$, column $y$ is denoted $(x, y)$.

Every second, Jinyoung chooses one direction among up, down, right, and left, and moves at least 1 and at most $K$ empty cells in that direction.

Given the start point $(x_1, y_1)$ and the end point $(x_2, y_2)$, find the minimum time to move from the start point to the end point.

The first line gives the size of the gym $N$ and $M$, and the maximum number of cells $K$ that can be moved in 1 second.

From the second line, $N$ lines give the state of the gym. Each cell of the gym is either empty or a wall, where an empty cell is given as '.', and a wall is given as '#'.

The last line gives four integers $x_1$, $y_1$, $x_2$, $y_2$. The two cells are different cells and are always empty.

Print the minimum time to move from $(x_1, y_1)$ to $(x_2, y_2)$. If it is impossible to move, print -1.

• $2 \le N, M \le 1\,000$
• $1 \le K \le 1\,000$
• $1 \le x_1, x_2 \le N$
• $1 \le y_1, y_2 \le M$