Centre for Gifted Education - Hanoi university of Technology

Sau khi princess Lem bị devil dragon bắt về làm vợ. Hiệp sĩ Zone lập tức lên đường tìm đến hang núi Gone nơi Dragon đang ẩn nấp để giải cứu công chúa. Đường đến Gone hết sức nguy hiểm, sau khi vượt qua ngàn nguy hiểm để đến được Gone, Zone phải vượt qua 1 mê cung với rất nhiều cạm bẫy để có thể đến nơi công chúa bị giam giữ. Mê cũng này rất đặc biệt vì thế không thể đi trực tiếp vào mê cung.

Mê cung trông giống như 1 ma trận M x N ô vuông đơn vị, trên đó có 1 số ô là cạm bẫy. Thật may mắn là Zone có thể sử dụng TELEPORT và anh ta đã đến được 1 ô không nguy hiểm ở trong mê cung. Nhưng Dragon đã khởi động các cạm bẫy, muốn cứu công chúa cách duy nhất là phải thoát ra khỏi mê cung. Khi đó Zone sẽ lại có thể sử dụng TELEPORT để cứu công chúa.

Đây là 1 bài toán áp dụng 2 thuật toán tìm kiếm DFS & BFS. Bạn hãy thử giải bài toán này để xem Zone đã thoát ra khỏi mê cung để cứu công chúa như thế nào. Biết rằng:

Mỗi lần di chuyển hiệp sĩ Zone chỉ có thể đi đến được 1 trong 4 ô kề cạnh và ô đó không có cạm bẫy. Zone không đi trên các ô đã từng đi qua.

Input

Dòng 1 gồm 2 số M, N là kích thược của mê cung ( 1 <= M, N <= 100 )

M dòng tiếp theo: Mỗi dòng gồm N số mô tả mê cung, mỗi ô có giá trị 1/0 tương ứng với ô đó có/không có cạm bẫy. Ô mà hiệp sĩ Zone đang đứng được đánh số 2

Output

Dòng 1 ghi số nguyên K là số bước di chuyển để hiệp sĩ Zone có thể thoát khỏi mê cung

K dòng tiếp theo: Mỗi dòng gồm 2 số nguyên i, j mô tả toạ độ di chuyển trên đường đi của Zone.

Example

Input:
5 5
1 1 1 1 1
1 0 0 0 1
1 2 1 0 1
1 1 0 0 1
1 1 0 1 1

Output:
8
3 2
2 2
2 3
2 4
3 4
4 4
4 3
5 3