Mê cung lưới

Cho một mê cung dạng lưới kích thước $n\times m$. Mỗi ô của lưới hoặc là ô trống, hoặc là một bức tường. Ta có thể đi từ ô này sang ô kia nếu cả hai đều là ô trống và chúng có chung một cạnh.

Trong mê cung ban đầu, tất cả các ô trống tạo thành một miền liên thông: từ một ô trống bất kỳ đều có thể đi tới mọi ô trống khác.

Hãy biến đúng $k$ ô trống thành tường sao cho các ô trống còn lại vẫn tạo thành một miền liên thông.

Dữ liệu đảm bảo luôn tồn tại đáp án. Nếu có nhiều cách, in ra cách nào cũng được.

Dữ liệu vào

• Dòng đầu 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 gồm $m$ ký tự mô tả mê cung ban đầu. Ký tự . là ô trống, ký tự # là tường.

Dữ liệu ra

In ra $n$ dòng, mỗi dòng gồm $m$ ký tự mô tả mê cung sau khi biến đổi. Những ô trống được biến thành tường phải được đánh dấu bằng ký tự X, các ô còn lại giữ nguyên ký tự ban đầu (. hoặc #).

Ràng buộc

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

Ví dụ