마르고, 메가바이트버그를 떠나다

최근 사건 때문에 마르고는 메가바이트버그를 떠나야 한다. 이 도시는 길이가 $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에 제출하면 빨라질 수 있다.