Марго покидает Мегабайтбург
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

В связи с некоторыми событиями Марго необходимо покинуть Мегабайтбург. Известно, что этот город представляет собой прямоугольную матрицу, длина которой равна $$$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 1
3 3
Выходные данные
NO
Входные данные
2 2 0
#.
..
1 2
2 1
Выходные данные
YES
Входные данные
2 5 2
.#.#.
###..
1 1
2 4
Выходные данные
YES

Примечание

Решение на языке Python можно ускорить, если отправить его на PyPy.