Olya thích nước tăng lực. Cô ấy thích chúng đến nỗi phòng của cô đầy những lon nước tăng lực rỗng.

Về mặt hình thức, phòng của cô có thể được biểu diễn như một lưới ô \(n \times m\), mỗi ô có thể trống hoặc đầy những lon nước.

Olya đã uống rất nhiều nước tăng lực, nên bây giờ cô có thể chạy \(k\) mét mỗi giây. Mỗi giây cô chọn một trong bốn hướng (lên, xuống, trái hoặc phải) và chạy từ \(1\) đến \(k\) mét theo hướng đó. Tất nhiên, cô chỉ có thể chạy qua các ô trống.

Bây giờ Olya cần phải đi từ ô \((x_1, y_1)\) đến ô \((x_2, y_2)\). Cô ấy sẽ mất bao nhiêu giây nếu cô ấy di chuyển tối ưu?

Đảm bảo rằng các ô \((x_1, y_1)\) và \((x_2, y_2)\) là trống. Những ô này có thể trùng nhau.

Input

• Dòng đầu tiên chứa ba số nguyên \(n\), \(m\) và \(k\) \((1 \leq n, m, k \leq 1000)\) - kích thước của phòng và tốc độ của Olya.
• Sau đó, \(n\) dòng tiếp theo chứa \(m\) ký tự mỗi dòng, ký tự thứ \(i\) trên vị trí \(j\) là #, nếu ô \((i, j)\) đầy lon, và . nếu ngược lại.
• Dòng cuối cùng chứa bốn số nguyên \(x_1, y_1, x_2, y_2\) \((1 \leq x_1, x_2 \leq n, 1 \leq y_1, y_2 \leq m)\) - tọa độ của ô bắt đầu và ô kết thúc.

Output

• In một số nguyên - thời gian tối thiểu để Olya đi từ \((x_1, y_1)\) đến \((x_2, y_2)\).
• Nếu không thể đi từ \((x_1, y_1)\) đến \((x_2, y_2)\), in \(-1\).

Example

3 4 4
....
###.
....
1 1 3 1

3

3 4 1
....
###.
....
1 1 3 1

8

2 2 1
.#
#.
1 1 2 2

-1