В связи с некоторыми событиями Марго необходимо покинуть Мегабайтбург. Известно, что этот город представляет собой прямоугольную матрицу, длина которой равна $$$M$$$, а высота – $$$N$$$. Клетки матрицы бывают двух типов: свободные (обозначаются символом '$$$.$$$') и занятые стеной (обозначаются символом '$$$\#$$$'). Марго может за один ход переместиться из клетки $$$(i, j)$$$ в любую из клеток $$$(i - 1, j)$$$, $$$(i + 1, j)$$$, $$$(i, j - 1)$$$, $$$(i, j + 1)$$$. Также Марго может не более $$$K$$$ раз совершить в качестве хода Мегапрыжок: из клетки $$$(i, j)$$$ попасть в любую из клеток $$$(i - 2, j)$$$, $$$(i + 2, j)$$$, $$$(i, j - 2)$$$, $$$(i, j + 2)$$$. При этом, вне зависимости от того, использовался ли Мегапрыжок или нет, Марго должен завершить свой ход в свободной клетке, которая находится внутри Мегабайтбурга. Общежитие, в котором сейчас находится Марго, расположено в клетке $$$(d_x, d_y)$$$, а аэропорт, в который Марго хочет попасть, – в клетке $$$(a_x, a_y)$$$. Гарантируется, что общежитие и аэропорт находятся в разных свободных клетках. Сейчас нет времени на размышления, поэтому требуется Ваша помощь. Выясните, может ли Марго добраться от общежития до аэропорта.
В первой строке даны числа $$$N, M, K~(2 \le N, M \le 1000, 0 \le K \le 10^6)$$$ – размеры Мегабайтбурга и количество доступных Марго Мегапрыжков.
В каждой из последующих $$$N$$$ строк дано $$$M$$$ символов '$$$.$$$' или '$$$\#$$$' – описание Мегабайтбурга.
В $$$N + 2$$$-й строке даны числа $$$d_x, d_y~(1 \le d_x \le N, 1 \le d_y \le M)$$$ – координаты общежития. Гарантируется, что данная клетка свободна.
В последней строке даны числа $$$a_x, a_y~(1 \le a_x \le N, 1 \le a_y \le M)$$$ – координаты аэропорта. Гарантируется, что данная клетка свободна.
Гарантируется, что координаты общежития не совпадают с координатами аэропорта.
Выведите «YES», если Марго может попасть из общежития в аэропорт. В противном случае выведите «NO». Ответ можно выводить в любом регистре.
3 3 1.#.#.#.#.1 13 3
NO
2 2 0#...1 22 1
YES
2 5 2.#.#.###..1 12 4
YES
Решение на языке Python можно ускорить, если отправить его на PyPy.