Olya and Energy Drinks

Olya는 에너지 음료를 좋아한다. 너무나 좋아한 나머지 그녀의 방은 에너지 음료의 빈 캔으로 가득하다.

형식적으로, 그녀의 방은 n × m개의 칸으로 이루어진 격자로 나타낼 수 있으며, 각 칸은 비어 있거나 캔이 널려 있다.

Olya는 에너지 음료를 많이 마셨기 때문에 이제 초당 k미터를 달릴 수 있다. 매초 그녀는 네 방향(위, 아래, 왼쪽 또는 오른쪽) 중 하나를 선택하고 그 방향으로 1미터 이상 k미터 이하를 달린다. 물론, 그녀는 빈 칸만 통과할 수 있다.

Now Olya는 (x1, y1) 칸에서 (x2, y2) 칸으로 가야 한다. 최적으로 이동한다면 몇 초가 걸리는가?

(x1, y1) 칸과 (x2, y2) 칸은 비어 있음이 보장된다. 이 두 칸은 같을 수도 있다.

첫 번째 줄에는 방의 크기와 Olya의 속도를 나타내는 세 정수 n, m, k (1 ≤ n, m, k ≤ 1000)가 주어진다.

이어서 각각 m개의 문자를 포함하는 n개의 줄이 주어진다. 그중 i-th번째 줄의 j-th번째 위치에는 (i, j) 칸에 캔이 널려 있으면 "#"이, 그렇지 않으면 "."이 주어진다.

마지막 줄에는 처음 칸과 마지막 칸의 좌표를 나타내는 네 정수 x1, y1, x2, y2 (1 ≤ x1, x2 ≤ n, 1 ≤ y1, y2 ≤ m)가 주어진다.

Olya가 (x1, y1)에서 (x2, y2)로 가는 데 걸리는 최소 시간을 나타내는 정수 하나를 출력한다.

(x1, y1)에서 (x2, y2)로 갈 수 없다면 -1을 출력한다.

첫 번째 예제에서 Olya는 첫 번째 초에 오른쪽으로 3미터, 두 번째 초에 아래로 2미터, 세 번째 초에 왼쪽으로 3미터를 달려야 한다.

두 번째 예제에서 Olya는 오른쪽으로 3초 동안 달린 다음 아래로 2초 동안 달리고, 그다음 왼쪽으로 3초 동안 달려야 한다.

Olya는 에너지 음료를 마시는 것을 권하지 않으며, 일반적으로 이것이 나쁘다고 생각한다.