Задача B. Balorant

Автор:Денис Лысенко   Ограничение времени:1 сек
Входной файл:Стандартный вход   Ограничение памяти:256 Мб
Выходной файл:Стандартный выход  
Максимальный балл:100  

Условие

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

Работа Антона заключается в проверке, сможет ли персонаж добраться из клетки с координатами (x1, y1) в клетку (x2, y2).

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

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

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

Во второй строке содержатся 4 целых числа x1, y1, x2, y2(1≤ x1,x2≤ n, 1≤ y1,y2m). В задаче гарантируется, что клетки (x1, y1) и (x2, y2) свободны.

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

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

Выведите одно единственное число - минимальное время, за которое Даон добежит из клетки (x1, y1) в клетку (x2, y2). Если Даон не может добраться из (x1, y1) в (x2, y2) - выведите  − 1.

Ограничения

(1≤ n,m,k≤ 1000)

(1≤ x1,x2≤ n, 1≤ y1,y2m)

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

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

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

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

Подзадача Баллы Дополнительные ограничения
nmk
1101 ≤ n ≤ 101 ≤ m ≤ 101 ≤ k ≤ 10
2351 ≤ n ≤ 1001 ≤ m ≤ 1001 ≤ k ≤ 100
3551 ≤ n ≤ 10001 ≤ m ≤ 10001 ≤ k ≤ 1000

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

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

Д-→Д

###↓

Д←-Д

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

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

Стандартный вход Стандартный выход
1
3 4 4
1 1 3 1
....
###.
....
3
2
2 2 1
1 1 2 2
.#
#.
-1

0.138s 0.016s 13