Mê cung và những bức tường

Cho một mê cung dạng lưới kích thước $n\times m$, trong đó mỗi ô là ô trống (ký hiệu .) hoặc ô tường (ký hiệu #). Hai ô trống được gọi là kề nhau nếu chúng có chung một cạnh. Ban đầu, tất cả các ô trống tạo thành một vùng liên thông — nghĩa là từ một ô trống bất kỳ, ta có thể di chuyển đến mọi ô trống khác bằng cách chỉ đi qua các ô trống kề nhau.

Bạn cần biến chính xác $k$ ô trống thành ô tường, đồng thời các ô trống còn lại vẫn phải tạo thành một vùng liên thông. Đảm bảo rằng luôn tồn tại lời giải.

Hãy in lại lưới sau khi biến đổi. Đánh dấu các ô trống được biến thành tường bằng ký tự X. Các ô tường gốc giữ nguyên ký tự #, các ô trống không bị biến đổi giữ nguyên ký tự ..

Nếu có nhiều cách thoả mãn, in ra một cách bất kỳ.

Dữ liệu vào

• Dòng đầu tiên chứa ba số nguyên $n$, $m$, $k$ — chiều cao, chiều rộng của mê cung và số ô trống cần biến thành tường.
• $n$ dòng tiếp theo, mỗi dòng chứa $m$ ký tự . hoặc #, mô tả mê cung ban đầu.

Dữ liệu ra

In ra $n$ dòng, mỗi dòng $m$ ký tự, mô tả mê cung sau khi biến đổi theo quy ước ở trên.

Ràng buộc

• $1\le n,m\le 500$
• $0\le k<s$, trong đó $s$ là số ô trống ban đầu.

Ví dụ