Задача B. Balorant ≡

Условие

Антона позвали на работу тестировщиком карт для одной популярной игры "Балорант". Антон уже давно играет в Балорант и знает всех персонажей. Тестировать карты он собирается на Даон - самом быстром персонаже в игре. Карта представляет собой клетчатое поле n * m, каждая клетка которого или свободна, или занята препятствием. Даон может передвигаться со скоростью до k клеток в секунду. Каждую секунду Антон может выбрать, в какую сторону будет бежать Даон (вверх, вниз, влево или вправо), после чего персонаж пробегает в этом направлении от 1 до k клеток. Разумеется, что Даон может передвигаться только по свободным клеткам карты.

Работа Антона заключается в проверке, сможет ли персонаж добраться из клетки с координатами (x₁, y₁) в клетку (x₂, y₂).

Антон очень ленивый и не собирается долго работать. Всё, что он хочет - сам поиграть в Балорант. Помогите Антону написать программу, которая будет определять, за какое минимальное количество секунд Даон сможет добежать из квадрата (x₁, y₁) в квадрат (x₂, y₂). Если геймдизайнеры продумали уровень плохо, и персонаж никак не может добраться до требуемой точки - программа должна вывести  − 1

Формат входных данных

В первой строке подаются целые числа n, m, k(1 ≤ n,m,k ≤ 1000) - размеры карты и скорость Даон.

Во второй строке содержатся 4 целых числа x₁, y₁, x₂, y₂(1 ≤ x₁,x₂ ≤ n, 1 ≤ y₁,y₂≤m). В задаче гарантируется, что клетки (x₁, y₁) и (x₂, y₂) свободны.

Далее следует n строк, каждая длиной m символов. Каждая i-ая строка содержит на j-ой позиции символ "." для свободной клетки или символ "#", если клетка занята препятствием.

Формат выходных данных

Выведите одно единственное число - минимальное время, за которое Даон добежит из клетки (x₁, y₁) в клетку (x₂, y₂). Если Даон не может добраться из (x₁, y₁) в (x₂, y₂) - выведите  − 1.

Ограничения

(1 ≤ n,m,k ≤ 1000)

(1 ≤ x₁,x₂ ≤ n, 1 ≤ y₁,y₂≤m)

Описание подзадач и системы оценивания

Баллы за каждую подзадачу начисляются только в случае, если все тесты этой подзадачи успешно пройдены.

Проверка каждой подзадачи выполняется до первой ошибки на каком-нибудь тесте этой подзадачи.

По запросу сообщается результат окончательной проверки на каждом тесте.

Пояснение к примерам

В первом примере Даон пробегает 3 клетки вправо, 2 клетки вниз и 3 клетки вправо. Ответ 3 секунды. Иллюстрация движения Даон в первом примере:

Д-→Д

###↓

Д←-Д

Во втором примере Даон не смогла дойти до требуемой точки, поэтому ответ -1

Примеры тестов

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

3

2 2 1
1 1 2 2
.#
#.

-1