Оля очень любит энергетики. Настолько сильно, что её комната завалена банками от энергетиков.
Более формально, её комнату можно представить в виде прямоугольного клетчатого поля размером n × m, каждая клетка которого либо завалена банками, либо свободна.
Оля выпила много энергетика и теперь может пробегать k метров за секунду. Каждую секунду она выбирает одно из четырех направлений (вверх, вниз, влево или вправо) и пробегает в нем от 1 до k метров. Конечно, она может бежать только через свободные клетки.
Сейчас Оле нужно попасть из клетки (x1, y1) в клетку (x2, y2). Сколько секунд ей потребуется, если она будет действовать оптимально?
Гарантируется, что клетки (x1, y1) и (x2, y2) свободны. Эти клетки могут совпадать.
Выходные данные
Выведите одно число — минимальное время, которое понадобится Оле, чтобы попасть из (x1, y1) в (x2, y2).
Если Оля не сможет добраться из (x1, y1) в (x2, y2), выведите -1.
Примечание
В первом примере Оля должна пробежать 3 метра вправо в первую секунду, 2 метра вниз во вторую и 3 метра влево в третью.
Во втором примере Оля должна 3 секунды бежать вправо, 2 секунды вниз и 3 секунды влево.
Оля не рекомендует пить энергетики и вообще считает, что это плохо.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 4 4
....
###.
....
1 1 3 1
|
3
|
|
2
|
3 4 1
....
###.
....
1 1 3 1
|
8
|
|
3
|
2 2 1
.#
#.
1 1 2 2
|
-1
|