President K rất thích giải các mê cung. Ông có một bản đồ dạng lưới hình chữ nhật gồm \(R\) hàng và \(C\) cột.
Mỗi ô trong lưới được tô màu trắng hoặc đen.
Ô ở hàng thứ \(i\) từ trên xuống và cột thứ \(j\) từ trái sang phải được gọi là ô \((i,j)\).
President K chỉ có thể di chuyển qua các ô màu trắng và không thể đi qua các ô màu đen.
Cụ thể, việc giải mê cung được thực hiện như sau:
- Chọn một ô trắng \((S_r, S_c)\) làm điểm bắt đầu và một ô trắng \((G_r, G_c)\) làm đích.
- Từ một ô trắng, có thể di chuyển sang một ô trắng kề cạnh theo một trong bốn hướng: trên, dưới, trái, phải.
Hiện tại, điểm bắt đầu và điểm đích đã được cố định.
Tuy nhiên, trong một số cấu hình màu của lưới, có thể không tồn tại đường đi chỉ qua các ô trắng từ điểm bắt đầu đến điểm đích.
President K có một con dấu hình vuông kích thước \(N \times N\).
Mỗi lần thực hiện một thao tác, ông chọn hai số nguyên \(a, b\) sao cho
\(1 \le a \le R - N + 1\) và \(1 \le b \le C - N + 1\),
sau đó tô trắng toàn bộ các ô \((i,j)\) thỏa mãn:
$
a \le i \le a + N - 1,\quad b \le j \le b + N - 1.
$
Do việc sử dụng con dấu khiến tay bị bẩn, President K muốn tối thiểu hóa số lần thao tác sao cho tồn tại một đường đi từ ô bắt đầu đến ô đích chỉ qua các ô trắng.
Hãy xác định số thao tác ít nhất cần thực hiện.
\InputFile
- Dòng đầu chứa ba số nguyên \(R, C, N\) \((1 \le N \le R \le C)\).
- Dòng thứ hai chứa hai số nguyên \(S_r, S_c\) --- tọa độ ô bắt đầu.
- Dòng thứ ba chứa hai số nguyên \(G_r, G_c\) --- tọa độ ô đích.
- \(R\) dòng tiếp theo, dòng thứ \(i\) là một xâu độ dài \(C\) gồm các ký tự
. hoặc #,
trong đó . biểu thị ô trắng và # biểu thị ô đen.
Dữ liệu đảm bảo rằng ô bắt đầu và ô đích đều là ô trắng.
\OutputFile
In ra một số nguyên --- số thao tác ít nhất cần thực hiện để tồn tại đường đi từ ô bắt đầu đến ô đích chỉ qua các ô trắng.
Trong tất cả mọi trường hợp
- \(R \times C \le 6\,000\,000\).
- \(1 \le S_r, G_r \le R\).
- \(1 \le S_c, G_c \le C\).
- \((S_r, S_c) \ne (G_r, G_c)\).
\Scoring
- Subtask 1 (11 điểm): \(N = 1\), \(R \times C \le 1\,500\,000\).
- Subtask 2 (19 điểm): \(R \times C \le 1\,000\).
- Subtask 3 (15 điểm): đáp án không vượt quá \(10\), \(R \times C \le 1\,500\,000\).
- Subtask 4 (19 điểm): \(R \times C \le 60\,000\).
- Subtask 5 (20 điểm): \(R \times C \le 1\,500\,000\).
- Subtask 6 (16 điểm): không có ràng buộc thêm.
Example
Test 1
Input
2 4 2
1 1
2 4
.###
###.
Output
1
Test 2
Input
6 6 1
1 6
6 1
..#.#.
##.###
####.#
...###
##.##.
.#.###
Output
4
