Mê Cung Hai Kiểu Di Chuyển

Một mê cung có $h$ hàng và $w$ cột. Ô $(r,c)$ là ô trống nếu ký tự tương ứng là ., và là tường nếu ký tự đó là #.

Bạn bắt đầu ở một ô trống $(s_r,s_c)$ và cần tới ô trống $(t_r,t_c)$. Có hai kiểu di chuyển:

• Đi bộ: sang một ô trống chung cạnh với ô hiện tại. Thao tác này không dùng phép thuật.
• Dịch chuyển: tới một ô trống $(r^{\prime },c^{\prime })$ thỏa $|r^{\prime }-r|\le 2$ và $|c^{\prime }-c|\le 2$. Thao tác này dùng đúng một lần phép thuật.

Khi dịch chuyển, các ô nằm giữa điểm đầu và điểm cuối không ảnh hưởng; chỉ ô đích cần là ô trống. Không thao tác nào được đưa bạn ra ngoài mê cung.

Hãy tìm số lần dùng phép thuật ít nhất để tới đích. Nếu không thể tới, in $-1$.

Input

• Dòng đầu chứa hai số nguyên $h$ và $w$.
• Dòng thứ hai chứa $s_r,s_c$ - tọa độ xuất phát.
• Dòng thứ ba chứa $t_r,t_c$ - tọa độ đích.
• Mỗi trong $h$ dòng tiếp theo chứa một xâu độ dài $w$ mô tả một hàng của mê cung.

Output

• In số lần dịch chuyển ít nhất, hoặc $-1$ nếu không tồn tại hành trình.

Constraints

• $1\le h,w\le 1000$.
• $1\le s_r,t_r\le h$.
• $1\le s_c,t_c\le w$.
• Mỗi ô là . hoặc #.
• Ô xuất phát và ô đích đều là ô trống và khác nhau.

Scoring

• Subtask $1$ ($50\%$ số điểm): $h,w\le 12$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

5 5
1 1
5 5
..#..
..#..
#####
..#..
..#..

1

4 6
1 2
4 5
......
.####.
......
......

0