D. Оля и энергетики
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Оля очень любит энергетики. Настолько сильно, что её комната завалена банками от энергетиков.

Более формально, её комнату можно представить в виде прямоугольного клетчатого поля размером n × m, каждая клетка которого либо завалена банками, либо свободна.

Оля выпила много энергетика и теперь может пробегать k метров за секунду. Каждую секунду она выбирает одно из четырех направлений (вверх, вниз, влево или вправо) и пробегает в нем от 1 до k метров. Конечно, она может бежать только через свободные клетки.

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

Гарантируется, что клетки (x1, y1) и (x2, y2) свободны. Эти клетки могут совпадать.

Входные данные

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

Далее следует n строк, каждая длиной m символов, i-я из которых содержит на j-й позиции «#», если клетка (i, j) завалена банками и «.» в противном случае.

Последняя строка содержит четыре целых числа x1, y1, x2, y2 (1 ≤ x1, x2 ≤ n, 1 ≤ y1, y2 ≤ m).

Выходные данные

Выведите одно число — минимальное время, которое понадобится Оле, чтобы попасть из (x1, y1) в (x2, y2).

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

Примеры
Входные данные
3 4 4
....
###.
....
1 1 3 1
Выходные данные
3
Входные данные
3 4 1
....
###.
....
1 1 3 1
Выходные данные
8
Входные данные
2 2 1
.#
#.
1 1 2 2
Выходные данные
-1
Примечание

В первом примере Оля должна пробежать 3 метра вправо в первую секунду, 2 метра вниз во вторую и 3 метра влево в третью.

Во втором примере Оля должна 3 секунды бежать вправо, 2 секунды вниз и 3 секунды влево.

Оля не рекомендует пить энергетики и вообще считает, что это плохо.