30592번 - Марго покидает Мегабайтбург 다국어

문제

В связи с некоторыми событиями Марго необходимо покинуть Мегабайтбург. Известно, что этот город представляет собой прямоугольную матрицу, длина которой равна $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>>. Ответ можно выводить в любом регистре.

제한

노트

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