미로

대통령 K는 미로 풀기를 좋아한다. 그는 미로를 만들 수 있는 격자 칸들을 찾아냈다. 격자는 가로 $R$행, 세로 $C$열로 이루어져 있고, 각 칸은 흰색 또는 검은색이다. 위에서 $i$번째 행($1 \le i \le R$)과 왼쪽에서 $j$번째 열($1 \le j \le C$)이 만나는 칸을 Cell $(i, j)$라고 한다.

K 대통령은 흰색 칸은 지날 수 있고 검은색 칸은 지날 수 없는 조건에서 미로를 푼다. 풀이 방법은 다음과 같다.

1. 흰색 칸 중에서 시작 칸 $(S_r, S_c)$와 목표 칸 $(G_r, G_c)$를 고른다.
2. 현재 칸에서 상하좌우로 인접한 흰색 칸으로 이동할 수 있다. 이를 반복해서 시작 칸부터 목표 칸까지 가는 경로를 찾는다.

시작 칸과 목표 칸은 이미 정해져 있다. 그런데 칸의 색에 따라서는 흰색 칸만으로 시작 칸에서 목표 칸까지 가는 경로가 없을 수 있다. K 대통령에게는 $N \times N$ 크기의 도장이 있다. 그는 다음 연산을 여러 번 수행해서 흰색 칸만으로 이루어진 경로가 시작 칸에서 목표 칸까지 생기도록 하려 한다.

연산: $N \times N$ 크기의 정사각형 영역을 골라 그 안의 모든 칸을 흰색으로 칠한다. 구체적으로 $1 \le a \le R - N + 1$, $1 \le b \le C - N + 1$을 만족하는 정수 $a$, $b$를 고르고, $a \le i \le a + N - 1$, $b \le j \le b + N - 1$을 만족하는 모든 Cell $(i, j)$를 흰색으로 칠한다.

도장을 쓰면 손이 더러워지므로 연산 횟수를 최소로 하려 한다. 칸의 색, 도장의 크기, 시작 칸과 목표 칸의 위치가 주어질 때, 흰색 칸만으로 이루어진 경로를 시작 칸에서 목표 칸까지 만드는 데 필요한 연산 횟수의 최솟값을 구하는 프로그램을 작성하라.

첫 번째 줄에 $R$, $C$, $N$이 주어진다.

두 번째 줄에 $S_r$과 $S_c$가 주어진다.

세 번째 줄에 $G_r$과 $G_c$가 주어진다.

이어서 $R$개의 줄에 길이 $C$의 문자열 $A_i$가 한 줄씩 주어진다. $A_i$의 $j$번째 문자가 .이면 Cell $(i, j)$는 흰색, #이면 검은색이다.

흰색 칸만으로 이루어진 경로를 시작 칸에서 목표 칸까지 만들기 위해 K 대통령이 수행해야 하는 연산 횟수의 최솟값을 한 줄에 출력한다.

• $1 \le N \le R \le C$.
• $R \times C \le 6\,000\,000$.
• $1 \le S_r \le R$, $1 \le S_c \le C$, $1 \le G_r \le R$, $1 \le G_c \le C$.
• $(S_r, S_c) \ne (G_r, G_c)$.
• $A_i$ ($1 \le i \le R$)는 .과 #으로 이루어진 길이 $C$의 문자열이다.
• Cell $(S_r, S_c)$와 Cell $(G_r, G_c)$는 흰색이다.
• $R$, $C$, $N$, $S_r$, $S_c$, $G_r$, $G_c$는 정수이다.