Trang trại của Tèo được điều hành tự động bằng một robot gieo hạt. Cánh đồng là lưới kích thước \(N \times M\), trong đó các ô được ký hiệu . là đất bằng phẳng có thể di chuyển, còn # là các hốc đá hoặc hào nước robot không thể vượt qua.

Robot xuất phát từ ô cổng vào tại góc trên bên trái (0, 0) và cần đi đến kho nhiên liệu ở ô góc dưới bên phải (N-1, M-1). Mỗi bước robot chỉ có thể di chuyển sang 4 ô kề cạnh (trên, dưới, trái, phải).

Hãy lập trình giúp robot tìm số bước di chuyển ít nhất và lộ trình chi tiết để tới kho nhiên liệu.

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên \(N\) và \(M\) (\(1 \le N, M \le 1000\)).
• \(N\) dòng tiếp theo, mỗi dòng chứa \(M\) ký tự mô tả bản đồ trang trại (. hoặc #).

Định dạng đầu ra

• Dòng đầu in ra số bước di chuyển tối thiểu, hoặc -1 nếu robot bị kẹt không thể tới kho.
• Nếu tới được, dòng tiếp theo in ra đường đi gồm tọa độ các ô dạng (r,c) cách nhau bởi dấu cách.

Ví dụ

Input:

3 3
...
.##
...

Output:

4
(0,0) (1,0) (2,0) (2,1) (2,2)