#1441. FENCE - Xây rào

Bản đồ một trang trại hình chữ nhật kích thước được chia làm lưới ô vuông đơn vị ( hàng, cột). Trên mỗi ô chứa một ký tự đánh dấu thuộc một trong ba loại:

• $: Ô chứa gà;
• *: Ô chứa cáo;
• .: Ô trống.

Người ta muốn xây rào quây một hình chữ nhật thỏa mãn:

• Hình chữ nhật có cạnh song song với cạnh trang trại và chứa trọn một số ô.
• Trong hình chữ nhật không chứa cáo;
• Số ô gà trong hình chữ nhật là nhiều nhất có thể;
• Nếu có nhiều cách xây rào thỏa mãn ba điều kiện trên, người ta muốn chọn hình chữ nhật có chu vi nhỏ nhất trong số đó (để tiết kiệm chi phí xây rào).

Yêu cầu: Tìm phương án xây rào.

Dữ liệu vào:

• Dòng đầu chứa hai số nguyên dương ;
• dòng tiếp theo, dòng chứa ký tự liền nhau, ký tự thứ cho biết trạng thái ô ;

Dữ liệu ra:

• Ghi ra số nguyên cách nhau bởi dấu cách trong đó:
  • : Chỉ số hàng nhỏ nhất;
  • : Chỉ số cột nhỏ nhất;
  • : Chỉ số hàng lớn nhất;
  • : Chỉ số cột lớn nhất của một ô bên trong rào.

Ví dụ:

Dữ liệu vào:

4 6
..$...
.*.$*.
$.$.$*
.$....

Dữ liệu ra:

3 1 4 5

Chú ý: Dữ liệu đảm bảo có ít nhất một ô gà.