Giải bài trực tuyến

Một ngày nọ, Tí Chuột tìm đường về hang của mình. Hang của Tí Chuột có rất nhiều cửa hang nằm rải rác trên các ô của một bảng hình chữ nhật kích thước M x N. Chỉ cần đi vào bất kỳ cửa hang nào là Tí Chuột sẽ về được chỗ ở của mình. Trên một số ô có vật cản và Tí Chuột không thể đi vào các ô đó. Mỗi bước Tí Chuột có thể đứng nguyên tại chỗ hoặc đi vào một trong 4 ô kề cạnh xung quanh. Tí Chuột rất thông minh, do đó nó luôn chọn đi theo ô nằm trong đường đi ngắn nhất để về hang. Nếu có nhiều lựa chọn, Tí Chuột sẽ ưu tiên theo thứ tự: đi lên trên, đi sang phải, đi xuống dưới, đi sang trái và đứng yên.

Tuy nhiên Bé Mèo không muốn Tí Chuột về được hang của mình. Bé Mèo cũng thông minh không kém; mỗi bước Bé Mèo sẽ tìm cách đặt một vật cản vào một ô trống, và tất nhiên phải là ô Tí Chuột không đang đứng. Mục tiêu của Bé Mèo là tìm cách đặt vật cản sao cho Tí Chuột không còn đường về hang nữa.

Bạn hãy lập trình giúp Bé Mèo đặt càng ít vật cản càng tốt để đạt được mục tiêu nhé! Biết rằng ở bước đi đầu tiên, Bé Mèo sẽ đặt vật cản trước, sau đó mới đến lượt Tí Chuột đi.

Input

Dòng đầu tiên chứa 2 số nguyên M và N (1 <= M, N <= 12).

M dòng tiếp theo, mỗi dòng chứa N ký tự mô tả bảng hình chữ nhật, trong đó ký tự '.' mô tả ô trống, ký tự 'O' mô tả một miệng hang, ký tự '#' mô tả vật cản và ký tự '*' mô tả vị trí ban đầu của Tí Chuột. Dữ liệu đảm bảo luôn có đúng một ký tự '*'.

Output

Dòng đầu tiên in ra số nguyên K là số vật cản Bé Mèo sẽ đặt. K dòng tiếp theo mỗi dòng chứa 2 số x, y là tọa độ dòng, cột của một vật cản Bé Mèo cần đặt. Các dòng của bảng được đánh số 1..M từ trên xuống, các cột được đánh số 1..N từ trái sang.

Điểm

K càng thấp bạn càng được điểm cao. Nếu cách đặt vật cản không hợp lệ hoặc sau khi đặt các vật cản Tí Chuột vẫn còn đường vào hang, bạn sẽ không nhận được điểm cho test tương ứng.

Example

Input:
3 3
..O
...
*..

Output:
3
2 2
1 1
3 2

Giải thích

Đầu tiên Bé Mèo đặt vật cản tại ô (2,2), Tí Chuột có thể đi sang ô (2,1) hoặc (3,2), tuy nhiên do Tí Chuột ưu tiên đi lên trên nên nó sẽ đi lên ô (2,1). Bé Mèo lại đặt vật cản tại ô (1,1), Tí Chuột phải quay về ô (3,1); Bé Mèo đặt vật cản tại ô (3,2) và thắng cuộc.