You are given a grid maze with height h and width w, which has floor cells marked with dots (.) and wall cells marked with hashtags (#). You are asked to mark k floor cells as walls. Yet, you should make sure that the remaining cells still form a connected area and that you don’t accidentally disconnect any part of a maze.
It’s guaranteed that the floor cells in the initial maze form a connected area.
The first line of the input contains 3 integers h, w (1 ≤ h, w ≤ 500), and k (0 ≤ k < n), where n is the number of floor cells in the initial grid.
The program should print any valid maze where k floor cells of the initial grid are marked as walls and there are no disconnected areas in the maze.
The newly marked walls should be represented with an X symbol.