Olya và đồ uống tăng lực

Cho một lưới $n\times m$ ô, mỗi ô hoặc trống (.) hoặc bị chặn (#). Bạn có thể di chuyển với tốc độ $k$ mét mỗi giây: mỗi giây, bạn chọn một trong bốn hướng (lên, xuống, trái, phải) và chạy từ $1$ đến $k$ ô liên tiếp theo hướng đó. Tất cả các ô bạn đi qua trong một giây (kể cả ô đích của giây đó) đều phải là ô trống.

Cho ô xuất phát $(x_1,y_1)$ và ô đích $(x_2,y_2)$, hãy tính số giây tối thiểu để đi từ $(x_1,y_1)$ đến $(x_2,y_2)$, hoặc thông báo nếu không thể đến được.

Dữ liệu vào

• Dòng đầu chứa ba số nguyên $n$, $m$, $k$.
• $n$ dòng tiếp theo, mỗi dòng gồm $m$ ký tự . hoặc # mô tả lưới.
• Dòng cuối chứa bốn số nguyên $x_1$, $y_1$, $x_2$, $y_2$. Hai ô $(x_1,y_1)$ và $(x_2,y_2)$ đều là ô trống và có thể trùng nhau.

Dữ liệu ra

In ra một số nguyên duy nhất — số giây tối thiểu cần thiết để đi từ $(x_1,y_1)$ đến $(x_2,y_2)$, hoặc $-1$ nếu không thể.

Ràng buộc

• $1\le n,m,k\le 1000$
• $1\le x_1,x_2\le n$
• $1\le y_1,y_2\le m$

Ví dụ