Trên một lưới ô vuông ~M \times N~ (~M, N < 1000~), người ta đặt robot A ở góc trái trên, robot B ở góc phải dưới. Mỗi ô của lưới có thể đặt một vật cản hoặc không (ô trái trên và phải dưới không có vật cản). Hai robot bắt đầu di chuyển đồng thời với tốc độ như nhau và không robot nào được dừng lại trong khi robot kia di chuyển (trừ khi nó không thể đi được nữa). Tại mỗi bước, robot chỉ có thể di chuyển theo 4 hướng - đi lên, đi xuống, sang trái, sang phải - vào các ô kề cạnh. Hai robot sẽ gặp nhau nếu chúng đứng trong cùng một ô vuông.

Yêu cầu: Hãy lập trình tìm cách di chuyển ít bước nhất mà 2 robot phải thực hiện để hai Robot có thể gặp nhau.

Input

• Dòng đầu ghi 2 số ~M, N~.
• ~M~ dòng tiếp theo, mỗi dòng ghi ~N~ số 0 hoặc 1 mô tả trạng thái của các ô vuông: 1 - có vật cản, 0 - không có vật cản. Các số trên cùng một dòng cách nhau ít nhất một khoảng trắng.

Output

• Nếu 2 robot không thể gặp nhau thì ghi ký tự #.
• Ngược lại, ghi số bước ít nhất để hai robot gặp nhau.

Sample Input 1

4 6
0 1 1 0 0 0
0 0 0 0 0 1
0 0 1 0 0 1
0 1 0 1 0 0

Sample Output 1

4