Vài ngày nữa là tới Nowruz, năm mới của Ba Tư. Ông nội đã mời các thành viên trong gia đình đến khu vườn của mình, trong đó có \(k\) đứa trẻ. Để buổi gặp mặt thêm vui, ông muốn tổ chức một trò chơi trốn tìm.

Khu vườn được biểu diễn bằng một lưới gồm \(m\) hàng và \(n\) cột ô vuông đơn vị. Một số ô, có thể không có ô nào, bị chặn bởi đá; các ô còn lại được gọi là ô tự do. Hai ô được gọi là lân cận nếu chúng có chung cạnh. Mỗi ô có tối đa bốn ô lân cận: hai ô theo chiều ngang và hai ô theo chiều dọc. Ông nội muốn biến khu vườn thành một mê cung bằng cách trồng bụi cây vào một số ô tự do. Những ô được trồng bụi cây không còn là ô tự do nữa.

Một mê cung phải thỏa mãn tính chất sau: với mỗi cặp ô tự do \(a\) và \(b\), có đúng một đường đi đơn giữa chúng. Đường đi đơn từ \(a\) đến \(b\) là một dãy các ô tự do, trong đó ô đầu tiên là \(a\), ô cuối cùng là \(b\), tất cả các ô đều phân biệt và hai ô liên tiếp luôn lân cận nhau.

Một đứa trẻ có thể trốn trong một ô khi và chỉ khi ô đó là ô tự do và có đúng một ô lân cận tự do. Không có hai đứa trẻ nào trốn trong cùng một ô.

Cho bản đồ khu vườn, hãy giúp ông nội tạo ra một mê cung có nhiều chỗ trốn cho trẻ nhỏ.

Cách nộp bài

Đây là bài chỉ nộp kết quả (output-only), có tính điểm thành phần. Bạn được cung cấp \(10\) tệp đầu vào, mỗi tệp mô tả một khu vườn. Với mỗi tệp đầu vào, bạn cần nộp một tệp đầu ra chứa bản đồ mê cung tương ứng. Điểm của từng tệp phụ thuộc vào số đứa trẻ có thể trốn trong mê cung bạn tạo ra.

Bạn không phải nộp mã nguồn cho bài này.

Dữ liệu vào

Mỗi tệp đầu vào có định dạng như sau:

• Dòng \(1\) chứa ba số nguyên \(m\), \(n\), \(k\): số hàng, số cột của khu vườn và số đứa trẻ được mời.
• Dòng \(1+i\), với \(1 \le i \le m\), chứa hàng thứ \(i\) của lưới: một xâu dài \(n\), không chứa ký tự trắng, chỉ gồm . và #.

Ký tự . biểu diễn ô tự do; ký tự # biểu diễn ô có đá.

Dữ liệu ra

Mỗi tệp đầu ra gồm \(m\) dòng. Dòng \(i\), với \(1 \le i \le m\), chứa hàng thứ \(i\) của mê cung sau khi trồng bụi cây: một xâu dài \(n\), không chứa ký tự trắng, gồm các ký tự sau:

• .: ô tự do.
• #: ô có đá.
• X: ô có bụi cây. Chữ X phải viết hoa.

Ràng buộc

• \(1 \le m,n \le 1024\).

Cách tính điểm

Một tệp đầu ra hợp lệ phải thỏa mãn cả hai điều kiện:

• Bản đồ đầu ra giống bản đồ đầu vào, ngoại trừ việc có thể thay một số lượng tùy ý các ký tự . bằng X.
• Bản đồ đầu ra có tính chất của một mê cung như đã định nghĩa ở trên.

Nếu đầu ra không hợp lệ, bạn nhận \(0\) điểm cho bộ dữ liệu đó. Nếu đầu ra hợp lệ, gọi \(l\) là số đứa trẻ có thể trốn trong mê cung, tức số ô tự do có đúng một ô lân cận tự do. Điểm của bộ dữ liệu là

được làm tròn xuống đến hai chữ số sau dấu thập phân. Ở đây, \(k\) là số được cho trong tệp đầu vào.

Bạn nhận đủ \(10\) điểm cho một bộ dữ liệu khi và chỉ khi đầu ra là một mê cung có ít nhất \(k\) chỗ trốn. Với mỗi bộ dữ liệu, luôn tồn tại một phương án đạt \(10\) điểm.

Nếu phương án hợp lệ nhưng điểm sau khi làm tròn xuống vẫn bằng \(0\), hệ thống CMS sẽ hiển thị kết quả Wrong Answer.

Phân nhóm

Mỗi tệp đầu vào chính thức tương ứng với một subtask, có điểm tối đa là \(10\). Tổng điểm tối đa của bài là \(100\).

Ví dụ

Dữ liệu vào

4 5 5
....#
.#..#
...#.
....#

Một đầu ra hợp lệ

.X.X#
.#..#
...#X
XX..#

Mê cung này có \(l=4\) chỗ trốn, nên phương án nhận được

điểm. Các chỗ trốn được đánh dấu bằng O trong lưới dưới đây. Ký tự O chỉ dùng để minh họa, không được dùng trong tệp đầu ra.

OXOX#
.#.O#
...#X
XX.O#

Các đầu ra không hợp lệ

Đầu ra thứ nhất:

.XXX#
.#XX#
...#.
XX..#

Không có đường đi đơn giữa ô tự do ở góc trên bên trái và ô tự do ở cột ngoài cùng bên phải.

Đầu ra thứ hai:

...X#
.#.X#
...#X
XXXX#

Đầu ra thứ ba:

XXXX#
X#XX#
..X#X
..XX#

Trong mỗi đầu ra thứ hai và thứ ba, giữa mỗi cặp ô tự do phân biệt có đúng hai đường đi đơn khác nhau, nên không thỏa mãn tính chất của mê cung.