Công ty JOI bán một trò chơi mô phỏng mang tên SimRoad. Trong trò chơi này, người chơi trở thành người cai trị một đất nước và thực hiện nhiều công việc để giúp đất nước phát triển thịnh vượng.

Đất nước trong trò chơi đang ở thời nguyên thủy. Các khu dân cư nằm rải rác, nhưng phần lớn đất đai bị cỏ cao bao phủ nên việc đi lại giữa các khu dân cư rất khó khăn. Nhiệm vụ đầu tiên của bạn là cắt cỏ để cư dân có thể dễ dàng đi lại giữa các khu dân cư.

Đất nước được chia thành một lưới gồm \(W\) ô theo hướng đông–tây và \(H\) ô theo hướng bắc–nam. Mỗi ô có một trong ba trạng thái: w nghĩa là ô bị cỏ bao phủ, . nghĩa là ô đất trống không có cỏ, còn @ nghĩa là ô có một khu dân cư.

Yêu cầu

Cư dân có thể tự do di chuyển đến ô kề bên theo một trong bốn hướng đông, tây, nam, bắc nếu ô đó là khu dân cư hoặc đất trống, nhưng không thể đi vào ô bị cỏ bao phủ. Bạn phải cắt cỏ ở một số ô để biến chúng thành đất trống, sao cho từ bất kỳ khu dân cư nào cũng có thể đi đến tất cả các khu dân cư khác.

Muốn cắt cỏ, bạn phải thuê cư dân làm việc; cắt cỏ ở một ô tốn \(1\) đô la. Để dành tiền cho sự phát triển về sau, bạn muốn chi tiêu càng ít càng tốt.

Có thể có nhiều cách cắt cỏ. Với trạng thái đất nước được cho, hãy tìm cách cắt cỏ ở càng ít ô càng tốt và tạo ra trạng thái đất nước sau khi cắt cỏ.

Đây là bài chỉ nộp kết quả (output-only). Bạn phải nộp các tệp kết quả cho năm tệp dữ liệu vào được cung cấp.

Thuật toán cơ bản

Đặt \(y'\) bằng \(H/2\) nếu \(H\) chẵn, và bằng \((H+1)/2\) nếu \(H\) lẻ:

Trước hết, cắt cỏ ở tất cả các ô bị cỏ bao phủ trên hàng thứ \(y'\) tính từ phía bắc. Sau đó, với mỗi khu dân cư, cắt hết cỏ trên đoạn theo hướng bắc–nam nối khu dân cư đó với ô ở hàng thứ \(y'\) tính từ phía bắc, trên cùng cột.

Dữ liệu vào

Có tất cả \(5\) tệp dữ liệu vào, mang tên simroad-ink.txt với \(k=1,2,3,4,5\), tức là simroad-in1.txt, simroad-in2.txt, simroad-in3.txt, simroad-in4.txt và simroad-in5.txt.

Tải bộ dữ liệu vào. Tệp ZIP gồm năm tệp 01.in, 02.in, 03.in, 04.in, 05.in, lần lượt tương ứng với simroad-in1.txt đến simroad-in5.txt trong đề.

Mỗi tệp có định dạng như sau:

• Dòng đầu chứa hai số nguyên \(W,H\), cách nhau bởi dấu cách.
• \(H\) dòng tiếp theo, mỗi dòng chứa một chuỗi gồm \(W\) ký tự, mô tả trạng thái đất nước. Ký tự thứ \(x\) trên dòng thứ \(y\) trong các dòng này là w, . hoặc @, biểu diễn trạng thái của ô thứ \(y\) tính từ phía bắc và thứ \(x\) tính từ phía tây.

Dữ liệu ra

Nộp dữ liệu ra dưới dạng tệp. Tên tệp là simroad-outk.txt với \(k=1,2,3,4,5\), tức là simroad-out1.txt, simroad-out2.txt, simroad-out3.txt, simroad-out4.txt và simroad-out5.txt. Tệp simroad-outk.txt phải chứa kết quả tương ứng với tệp simroad-ink.txt.

Mỗi tệp kết quả mô tả trạng thái đất nước sau khi cắt cỏ, gồm \(H\) dòng, mỗi dòng có đúng \(W\) ký tự. Ký tự thứ \(x\) trên dòng thứ \(y\) phải là w, . hoặc @, biểu diễn trạng thái của ô thứ \(y\) tính từ phía bắc và thứ \(x\) tính từ phía tây.

Chỉ được thay các ô w đã cắt cỏ bằng .; các ô khác giữ nguyên trạng thái. Không ghi dòng kích thước \(W,H\) vào tệp kết quả.

Ràng buộc

• \(1\le W\le100\): số ô theo hướng đông–tây.
• \(1\le H\le100\): số ô theo hướng bắc–nam.

Phân nhóm

• Có \(5\) bộ dữ liệu, mỗi bộ tối đa \(20\) điểm, tổng cộng \(100\) điểm.

Điểm của mỗi bộ dữ liệu phụ thuộc vào trạng thái đất nước trong tệp kết quả bạn nộp. Nếu kết quả không đáp ứng yêu cầu của bài toán thì bạn nhận \(0\) điểm cho bộ dữ liệu đó. Nếu kết quả đáp ứng yêu cầu, điểm được tính như sau.

Gọi:

• \(E_y\) là số tiền cần chi để tạo ra trạng thái đất nước trong kết quả bạn nộp.
• \(E_b\) là số tiền cần chi để tạo ra trạng thái đất nước do thuật toán cơ bản sinh ra.
• \(E_m\) là số tiền nhỏ nhất cần chi để tạo ra một trạng thái đất nước trong các kết quả do các thí sinh tham gia kỳ thi nộp.

Giá trị dùng để tính điểm là:

Điểm của bạn là giá trị trên được làm tròn đến một chữ số sau dấu phẩy: xét chữ số thứ hai sau dấu phẩy, nếu chữ số đó từ \(5\) trở lên thì làm tròn lên, nếu nhỏ hơn \(5\) thì làm tròn xuống.

Ví dụ

7 5
w@ww@w@
w.wwwww
wwww@ww
@wwwwww
ww@.@w.

w@..@.@
w.ww.ww
wwww@ww
@www.ww
..@.@w.

w@ww@w@
w.ww.w.
....@..
@w.w.ww
ww@.@w.