JOI thích trượt băng trên một sân băng rộng lớn giữa thiên nhiên.

Sân băng được biểu diễn bằng một hình chữ nhật gồm \(R\) hàng theo hướng bắc–nam và \(C\) cột theo hướng đông–tây. Gọi ô ở hàng thứ \(r\) tính từ phía bắc, cột thứ \(c\) tính từ phía tây là ô \((r,c)\). Mỗi ô hoặc có thể đi qua, hoặc chứa một khối băng và không thể đi qua. Tất cả các ô trên biên sân đều chứa khối băng, nên JOI không thể trượt ra ngoài sân. Cụ thể, các ô \((i,1)\), \((i,C)\) với \(1 \le i \le R\) và các ô \((1,j)\), \((R,j)\) với \(1 \le j \le C\) đều chứa khối băng.

JOI trượt băng không giỏi lắm. Mỗi lần di chuyển, cậu đạp vào ô đang đứng để trượt theo một trong bốn hướng đông, tây, nam, bắc và chỉ dừng lại ở ô ngay trước khối băng đầu tiên gặp phải. Quá trình từ lúc đạp vào mặt sân đến lúc dừng lại được tính là một lần di chuyển. Nếu ô liền kề theo một hướng chứa khối băng, cậu không thể di chuyển theo hướng đó.

Một hôm, khi đang trượt băng, JOI phát hiện rằng mỗi khi cậu đạp vào mặt sân, một khối băng sẽ mọc lên tại chính ô đó. Các ô cậu trượt qua, ngoại trừ ô đạp chân để bắt đầu di chuyển, không xuất hiện khối băng. Tiếp tục trượt trong tình trạng này rất nguy hiểm, nên JOI muốn thoát khỏi sân băng càng nhanh càng tốt.

Hiện tại JOI đang ở ô \((r_1,c_1)\). Để thoát khỏi sân băng, cậu phải dừng lại tại ô lối ra \((r_2,c_2)\). Chỉ trượt ngang qua ô lối ra trong một lần di chuyển là chưa đủ để thoát. Tùy trạng thái sân và vị trí ban đầu, có thể không có cách nào để cậu dừng tại lối ra.

Yêu cầu

Cho vị trí các khối băng, vị trí hiện tại của JOI và vị trí lối ra. Hãy xác định JOI có thể bắt đầu từ vị trí hiện tại và dừng tại lối ra hay không; nếu có, tìm số lần di chuyển ít nhất cần thực hiện.

Dữ liệu vào

Đọc từ đầu vào chuẩn:

• Dòng đầu chứa hai số nguyên \(R,C\), cách nhau bởi một dấu cách, là kích thước sân băng.
• \(R\) dòng tiếp theo, mỗi dòng chứa một xâu gồm \(C\) ký tự . hoặc #. Ký tự thứ \(c\) trên dòng thứ \(r\) trong số này mô tả trạng thái ban đầu của ô \((r,c)\): . là ô có thể đi qua, còn # là ô chứa khối băng và không thể đi qua.
• Dòng tiếp theo chứa hai số nguyên \(r_1,c_1\), cách nhau bởi một dấu cách, là vị trí hiện tại của JOI.
• Dòng tiếp theo chứa hai số nguyên \(r_2,c_2\), cách nhau bởi một dấu cách, là vị trí lối ra.

Dữ liệu ra

In ra đầu ra chuẩn một số nguyên trên một dòng: số lần di chuyển ít nhất để JOI dừng tại ô lối ra. Nếu không thể dừng tại ô lối ra bằng bất kỳ cách di chuyển nào, in -1.

Giới hạn

• \(3 \le R \le 1\,000\).
• \(3 \le C \le 1\,000\).
• \(1 \le r_1 \le R\).
• \(1 \le c_1 \le C\).
• \(1 \le r_2 \le R\).
• \(1 \le c_2 \le C\).
• Tất cả các ô trên biên đều chứa khối băng: \((i,1)\), \((i,C)\) với \(1 \le i \le R\) và \((1,j)\), \((R,j)\) với \(1 \le j \le C\).
• Hai ô \((r_1,c_1)\) và \((r_2,c_2)\) không chứa khối băng.

Chấm điểm

1. 13 điểm: \(R \le 10\), \(C \le 10\). Nếu có thể dừng tại lối ra, số lần di chuyển ít nhất không vượt quá \(10\).
2. 65 điểm: \(R \le 200\), \(C \le 200\).
3. 22 điểm: Không có giới hạn bổ sung.

Ví dụ

5 5
#####
#...#
#...#
#...#
#####
2 2
3 3

4

8 6
######
#..#.#
##...#
#....#
#.#..#
#....#
##...#
######
4 3
6 4

5

5 5
#####
#.#.#
#.#.#
#.#.#
#####
2 2
4 4

-1

3 3
###
#.#
###
2 2
2 2

0