Problem: Pavel loves grid mazes. A grid maze is an n × m rectangle maze where each cell is either empty, or is a wall. You can go from one cell to another only if both cells are empty and have a common side.

Pavel drew a grid maze with all empty cells forming a connected area. That is, you can go from any empty cell to any other one. Pavel doesn't like it when his maze has too little walls. He wants to turn exactly k empty cells into walls so that all the remaining cells still formed a connected area. Help him.

Input

The first line contains three integers n, m, k (1 ≤ n, m ≤ 500, 0 ≤ k < s), where n and m are the maze's height and width, correspondingly, k is the number of walls Pavel wants to add and letter s represents the number of empty cells in the original maze.

Each of the next n lines contains m characters. They describe the original maze. If a character on a line equals ".", then the corresponding cell is empty and if the character equals "#", then the cell is a wall.

Output

Print n lines containing m characters each: the new maze that fits Pavel's requirements. Mark the empty cells that you transformed into walls as "X", the other cells must be left without changes (that is, "." and "#").

It is guaranteed that a solution exists. If there are multiple solutions you can output any of them.

Examples

Input

3 4 2
#..#
..#.
#...


Output

#.X#
X.#.
#...


Input

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


Output

#XXX
#X#.
X#..
...#
.#.#

Solution (in PYTHON3):

Solution:
import time
visit=[0 for i in range(250005)]
class Graph(object):
    def __init__(self, graph_dict=None):
        """ initializes a graph object
            If no dictionary or None is given,
            an empty dictionary will be used
        """
        if graph_dict == None:
            graph_dict = {}
            self.num_vertices = 0
        else:
            self.num_vertices = len(graph_dict)
            self.__graph_dict = graph_dict

    def vertices(self):
        """ returns the vertices of a graph """
        return list(self.__graph_dict.keys())

    def edges(self):
        """ returns the edges of a graph """
        return self.__generate_edges()

    def add_vertex(self, vertex):
        """ If the vertex "vertex" is not in
            self.__graph_dict, a key "vertex" with an empty
            list as a value is added to the dictionary.
            Otherwise nothing has to be done.
        """

        if vertex not in self.__graph_dict:
            self.__graph_dict[vertex] = []
            self.num_vertices += 1

    def add_edge(self, edge):
        """ assumes that edge is of type set, tuple or list;
            between two vertices can be multiple edges!
        """
        #assuming vertex1 is FROMvertex and vertex2 is TOvertex
        edge=set(edge)
        (vertex1, vertex2) = tuple(edge)

        if (vertex1 not in self.__graph_dict):
            self.add_vertex(vertex1)
        if (vertex2 not in self.__graph_dict):
            self.add_vertex(vertex2)


        if vertex1 in self.__graph_dict:
            if vertex2 not in self.__graph_dict[vertex1]:
                self.__graph_dict[vertex1].append(vertex2)              #vertex already exists

        if vertex2 in self.__graph_dict:
            if vertex1 not in self.__graph_dict[vertex2]:
                self.__graph_dict[vertex2].append(vertex1)



    def __generate_edges(self):
        """ A static method generating the edges of the
            graph "graph". Edges are represented as sets
            with one (a loop back to the vertex) or two
            vertices
        """
        edges = []
        for vertex in self.__graph_dict:
            for neighbour in self.__graph_dict[vertex]:
                if {neighbour, vertex} not in edges:

                    edges.append({vertex, neighbour})
        return edges

    def __str__(self):
        res = "vertices: "
        for k in self.__graph_dict:
            res += str(k) + " "
        res += "\nedges: "
        for edge in self.__generate_edges():
            res += str(edge) + " "
        return res

        graph = self.__graph_dict
        isolated = []
        for vertex in graph:
            print(isolated, vertex)
            if not graph[vertex]:
                isolated += [vertex]
        return isolated

    def find_path(self, start_vertex, end_vertex, path=[]):
        """ find a path from start_vertex to end_vertex
            in graph """
        graph = self.__graph_dict
        path = path + [start_vertex]
        if start_vertex == end_vertex:
            return path
        if start_vertex not in graph:
            return None
        for vertex in graph[start_vertex]:
            if vertex not in path:
                extended_path = self.find_path(vertex,
                                               end_vertex,
                                               path)
                if extended_path:
                    return extended_path
        return None

    def BFS(self, s):
        graph = self.__graph_dict
        visited = [False] * (len(graph))
        queue = []
        arr = []
        i = 0
        queue.append(s)
        visited[i] = True
        i+=1
        while queue:

            s = queue.pop(0)
            arr.append(s)
            print(s, end=" ")

            for adj in graph[s]:
                if adj in arr:
                    if visited[arr.index(adj)] == False:
                        queue.append(adj)
                        visited[adj] = True
                else:
                    queue.append(adj)
                    visited[i] = True
                    i+=1

    def DFS(self, s):
        graph = self.__graph_dict
        visited = [False] * (len(graph))
        stack = []
        arr=[]


        stack.append(s)
        i=0
        visited[i] = True
        i+=1
        while stack:
            s = stack.pop()
            arr.append(s)
            print(s, end=" ")

            for adj in graph[s]:
                if adj in arr:
                    if visited[arr.index(adj)] == False:
                        stack.append(adj)
                        visited[adj] = True
                else:
                    stack.append(adj)
                    visited[i] = True
                    i+=1


    def find_all_paths(self, start_vertex, end_vertex, path=[]):
        """ find all paths from start_vertex to
            end_vertex in graph """
        graph = self.__graph_dict
        path = path + [start_vertex]
        if start_vertex == end_vertex:
            return [path]
        if start_vertex not in graph:
            return []
        paths = []
        for vertex in graph[start_vertex]:
            if vertex not in path:
                extended_paths = self.find_all_paths(vertex,
                                                     end_vertex,
                                                     path)
                for p in extended_paths:
                    paths.append(p)
        return paths

    def is_connected(self,vertices_encountered=None,start_vertex=None):
        """ determines if the graph is connected """
        if vertices_encountered is None:
            vertices_encountered = set()
        gdict = self.__graph_dict
        vertices = gdict.keys()
        if not start_vertex:
            # chosse a vertex from graph as a starting point
            start_vertex = vertices[0]
        vertices_encountered.add(start_vertex)
        if len(vertices_encountered) != len(vertices):
            for vertex in gdict[start_vertex]:
                if vertex not in vertices_encountered:
                    if self.is_connected(vertices_encountered, vertex):
                        return True
        else:
            return True
        return False

    def vertex_degree(self, vertex):
        """ The degree of a vertex is the number of edges connecting
            it, i.e. the number of adjacent vertices. Loops are counted
            double, i.e. every occurence of vertex in the list
            of adjacent vertices. """
        adj_vertices = self.__graph_dict[vertex]
        degree = len(adj_vertices) + adj_vertices.count(vertex)
        return degree

    def degree_sequence(self):
        """ calculates the degree sequence """
        seq = []
        for vertex in self.__graph_dict:
            seq.append(self.vertex_degree(vertex))
        seq.sort(reverse=True)
        return tuple(seq)

    @staticmethod
    def is_degree_sequence(sequence):
        """ Method returns True, if the sequence "sequence" is a
            degree sequence, i.e. a non-increasing sequence.
            Otherwise False is returned.
        """
        # check if the sequence sequence is non-increasing:
        return all(x >= y for x, y in zip(sequence, sequence[1:]))

    def delta(self):
        """ the minimum degree of the vertices """
        min = 100000000
        for vertex in self.__graph_dict:
            vertex_degree = self.vertex_degree(vertex)
            if vertex_degree < min:
                min = vertex_degree
        return min

    def Delta(self):
        """ the maximum degree of the vertices """
        max = 0
        for vertex in self.__graph_dict:
            vertex_degree = self.vertex_degree(vertex)
            if vertex_degree > max:
                max = vertex_degree
        return max

    def density(self):
        """ method to calculate the density of a graph """
        g = self.__graph_dict
        V = len(g.keys())
        E = len(self.edges())
        return 2.0 * E / (V * (V - 1))

    def diameter(self):
        """ calculates the diameter of the graph """

        v = self.vertices()
        pairs = [(v[i], v[j]) for i in range(len(v) - 1) for j in range(i + 1, len(v))]
        smallest_paths = []
        for (s, e) in pairs:
            paths = self.find_all_paths(s, e)
            smallest = sorted(paths, key=len)[0]
            smallest_paths.append(smallest)

        smallest_paths.sort(key=len)

        # longest path is at the end of list,
        # i.e. diameter corresponds to the length of this path
        diameter = len(smallest_paths[-1])
        return diameter

    def DFSnow(self, s,s1,k,a,n,m):
        graph = self.__graph_dict
        visited = [False] * (len(graph))
        stack = []
        arr=[]


        stack.append(s)
        i=0
        visited[i] = True
        i+=1

        while stack:
            s = stack.pop()
            arr.append(s)


            if(i-1==s1-k):

                for i in range(n):
                    for j in range(m):
                        if a[i][j]!=0 and a[i][j] not in arr:
                            print("X",end="")
                        elif a[i][j]==0:
                            print("#",end="")
                        elif a[i][j]!=0 and a[i][j] in arr:
                            print(".", end="")
                    print("\n")

                return

            for adj in graph[s]:
                if adj in arr:
                    if visited[arr.index(adj)] == False:
                        stack.append(adj)
                        visited[adj] = True
                else:
                    stack.append(adj)
                    visited[i] = True
                    i+=1

    def DFSnew(self, s,s1,k,a,n,m):
        graph = self.__graph_dict

        stack = []
        stack.append(s)
        co=0
        visit[1]=1

        while stack:

            s=stack.pop()
            #print(s,end=" ")
            visit[s]+=1
            co+=1

            if(co==s1-k):

                for i in range(n):
                    for j in range(m):
                        if a[i][j]:
                            if visit[a[i][j]]==2:
                                print(".", end="")
                            else:
                                print("X",end="")
                        else:
                            print("#",end="")

                    print("\n")

                return None

            for adj in graph[s]:
                if visit[adj] == 0:
                    stack.append(adj)
                    visit[adj] = 1

    def BFSnew(self, s,s1,k,a,n,m):
        graph = self.__graph_dict

        queue = []
        queue.append(s)
        co=0


        while queue:

            s=queue.pop(0)
            visit[s]=1
            co+=1

            if(co==s1-k):
                for i in range(n):
                    for j in range(m):
                        if a[i][j]:
                            if visit[a[i][j]]:
                                print(".", end="")
                            else:
                                print("X",end="")
                        else:
                            print("#",end="")

                    print("\n")

                return None

            for adj in graph[s]:
                if visit[adj] == 0:
                    queue.append(adj)


    @staticmethod
    def erdoes_gallai(dsequence):
        """ Checks if the condition of the Erdoes-Gallai inequality
            is fullfilled
        """
        if sum(dsequence) % 2:
            # sum of sequence is odd
            return False
        if Graph.is_degree_sequence(dsequence):
            for k in range(1, len(dsequence) + 1):
                left = sum(dsequence[:k])
                right = k * (k - 1) + sum([min(x, k) for x in dsequence[k:]])
                if left > right:
                    return False
        else:
            # sequence is increasing
            return False
        return True



if __name__ == "__main__":
    ts=time.time()
    g=dict()
    graph=Graph(g)
    b=list(map(int,input().split(" ")))
    n,m,k=b[0],b[1],b[2]
    c=[]
    for i in range(n):
        c.append(input())

    s=0
    a=[[0 for i in range(m)]for j in range(n)]

    for i in range(n):
        for j in range(m):
            if c[i][j]=='.':
                a[i][j]=s+1
                s+=1
            else:
                a[i][j]=0

    for i in range(n):
        for j in range(m):
            if a[i][j]:
                graph.add_vertex(a[i][j])
                if i-1>-1:
                    if(a[i-1][j]):
                        graph.add_edge({a[i][j],a[i-1][j]})
                if(i+1<n):
                    if (a[i+1][j]):
                        graph.add_edge({a[i][j], a[i+1][j]})
                if (j-1 > -1):
                    if (a[i][j-1]):
                        graph.add_edge({a[i][j], a[i][j-1]})
                if (j + 1 < m):
                    if (a[i][j+1]):
                        graph.add_edge({a[i][j], a[i][j+1]})


    graph.DFSnew(1,s,k,a,n,m)