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#..
...#
.#.#

Difficulty: competition

Starter code:

Solutions:
import sys

n, m, k = (int(x) for x in sys.stdin.readline().split(' '))
maze = []
for i in range(n):
    maze.append(list(sys.stdin.readline().strip()))

for y in range(n):
    for x in range(m):
        if maze[y][x] == '.':
            x0, y0 = x, y
            break
    else:
        continue
    break
else:
    print('no spare room')
    return

stack = []
stack.append((x0,y0))
while stack:
    x, y = stack[-1]

    if maze[y][x] == '.':
        maze[y][x] = '0'
        if x > 0 and maze[y][x-1] == '.':
            stack.append((x-1, y))
    elif maze[y][x] == '0':
        maze[y][x] = '1'
        if y < n-1 and maze[y+1][x] == '.':
            stack.append((x, y+1))
    elif maze[y][x] == '1':
        maze[y][x] = '2'
        if x < m-1 and maze[y][x+1] == '.':
            stack.append((x+1, y))
    elif maze[y][x] == '2':
        maze[y][x] = '3'
        if y > 0 and maze[y-1][x] == '.':
            stack.append((x, y-1))
    elif maze[y][x] == '3':
        if k > 0:
            maze[y][x] = 'X'
            k -= 1
        stack.pop()

for y in range(n):
    for x in range(m):
        maze[y][x] = '.' if maze[y][x] == '3' else maze[y][x]

print("\n".join(["".join(s) for s in maze]))


n, m, k = list(map(int, input().split()))
t = [input().replace('.', 'X') for i in range(n)]
k = n * m - k - sum(i.count('#') for i in t)
t = [list(i) for i in t]
i, p = 0, []
while k:
    if 'X' in t[i]:
        j = t[i].index('X')
        t[i][j], p = '.', [(i, j)]
        k -= 1
        break
    i += 1
while k:
    x, y = p.pop()
    for i, j in ((x, y - 1), (x, y + 1), (x - 1, y), (x + 1, y)):
        if i < 0 or j < 0: continue
        if i < n and j < m and t[i][j] == 'X':
            t[i][j] = '.'
            p.append((i, j))
            k -= 1
            if k == 0: break
for i in range(n): t[i] = ''.join(t[i])
print('\n'.join(t))


a, b, c = map(int, input().split(' '))
array = [[i for i in input()] for j in range(a)]
p = []
x = 0
for i in range(a):
    for j in range(b):
        if array[i][j] == '.':
            p = [(i, j)]
            x += 1

visited = [[False for _ in range(b)] for i in range(a)]
def ok(i, j):
    if 0 <= i <= a-1 and 0 <= j <= b-1:
        if array[i][j] == '.':
            return True
    return False

sa = 0
while sa < x-c:
    i, j = p[-1]
    p.pop()
    #print(i,j,sa)
    if not visited[i][j]:
        if ok(i, j-1):
            if not visited[i][j-1]:
                p.append((i, j-1))
        if ok(i, j+1):
            if not visited[i][j+1]:
                p.append((i, j+1))
        if ok(i+1, j):
            if not visited[i+1][j]:
                p.append((i+1, j))
        if ok(i-1, j):
            if not visited[i-1][j]:
                p.append((i-1, j))
        visited[i][j] = True
        sa+=1

for i in range(a):
    for j in range(b):
        if array[i][j] == '.' and not visited[i][j]:
            array[i][j] = 'X'

for each in [''.join(i) for i in array]:
    print(each)

a, b, c = map(int, input().split(' '))
array = [[i for i in input()] for j in range(a)]

p = []
x = 0
for i in range(a):
    for j in range(b):
        if array[i][j] == '.':
            x += 1
for i in range(a):
    for j in range(b):
        if array[i][j] == '.':
            p.append((i,j))
            break
visited = [[False for _ in range(b)] for i in range(a)]
def ok(i, j):
    if 0 <= i <= a-1 and 0 <= j <= b-1:
        if array[i][j] == '.':
            return True
    return False

sa = 0
while sa < x-c:
    i, j = p.pop()
    if visited[i][j]:
        continue
    #print(i,j,sa)
    if ok(i, j-1):
        if not visited[i][j-1]:
            p.append((i, j-1))
    if ok(i, j+1):
        if not visited[i][j+1]:
            p.append((i, j+1))
    if ok(i+1, j):
        if not visited[i+1][j]:
            p.append((i+1, j))
    if ok(i-1, j):
        if not visited[i-1][j]:
            p.append((i-1, j))
    visited[i][j] = True
    sa+=1

for i in range(a):
    for j in range(b):
        if array[i][j] == '.' and not visited[i][j]:
            array[i][j] = 'X'

for each in [''.join(i) for i in array]:
    print(each)

a, b, c = map(int, input().split(' '))
array = [[i for i in input()] for j in range(a)]
p = []
x = 0
for i in range(a):
    for j in range(b):
        if array[i][j] == '.':
            p.append((i, j))
            x += 1

visited = [[False] * b for i in range(a)]
def ok(i, j):
    if 0 <= i <= a-1 and 0 <= j <= b-1:
        if array[i][j] != '#':
            return True
    return False
sa = 0
while sa < x-c:
    i, j = p.pop()
    
    if visited[i][j]:
    
        continue
    if ok(i, j-1):
        if not visited[i][j-1]:
            p.append((i, j-1))

    if ok(i, j+1):
        if not visited[i][j+1]:
            p.append((i, j+1))

    if ok(i+1, j):
        if not visited[i+1][j]:
            p.append((i+1, j))

    if ok(i-1, j):
        if not visited[i-1][j]:
            p.append((i-1, j))
     
    visited[i][j] = True
    sa += 1

for i in range(a):
    for j in range(b):
        if array[i][j] == '.' and not visited[i][j]:
            array[i][j] = 'X'

for each in [''.join(i) for i in array]:
    print(each)

def main():
    n, m, k = map(int, input().split())
    mn = m * n
    l = [_ == '.' for _ in range(n) for _ in input()]
    neigh = [[] for _ in range(mn)]
    for y in range(n - 1):
        for x in range(m):
            yx = y * m + x
            if l[yx] and l[yx + m]:
                neigh[yx].append(yx + m)
                neigh[yx + m].append(yx)
    for y in range(n):
        for x in range(m - 1):
            yx = y * m + x
            if l[yx] and l[yx + 1]:
                neigh[yx].append(yx + 1)
                neigh[yx + 1].append(yx)
    res = [True] * mn
    nxt = {l.index(True)}
    cnt = sum(l) - k
    while cnt:
        cur, nxt = nxt, set()
        for i in cur:
            if res[i]:
                res[i] = False
                cnt -= 1
                if not cnt:
                    break
                for j in neigh[i]:
                    nxt.add(j)
    for x, (a, b) in enumerate(zip(res, l)):
        if a and b:
            l[x] = 2
    l = [''.join(('#', '.', 'X')[_] for _ in l[x:x + m]) for x in range(0, mn, m)]
    print('\n'.join(l))


def __starting_point():
    main()
__starting_point()

def main():
    n, m, k = map(int, input().split())
    mn = m * n
    l = [_ == '.' for _ in range(n) for _ in input()]
    neigh = [[] for _ in range(mn)]
    for y in range(n - 1):
        for x in range(m):
            yx = y * m + x
            if l[yx] and l[yx + m]:
                neigh[yx].append(yx + m)
                neigh[yx + m].append(yx)
    for y in range(n):
        for x in range(m - 1):
            yx = y * m + x
            if l[yx] and l[yx + 1]:
                neigh[yx].append(yx + 1)
                neigh[yx + 1].append(yx)
    res = [True] * mn
    cur, nxt = [], [l.index(True)]
    cnt = sum(l) - k
    while cnt:
        cur, nxt = nxt, cur
        nxt.clear()
        for i in cur:
            if res[i]:
                res[i] = False
                cnt -= 1
                if not cnt:
                    break
                for j in neigh[i]:
                    if res[j]:
                        nxt.append(j)
    for x, (a, b) in enumerate(zip(res, l)):
        if a and b:
            l[x] = 2
    l = [''.join(('#', '.', 'X')[_] for _ in l[x:x + m]) for x in range(0, mn, m)]
    print('\n'.join(l))


def __starting_point():
    main()
__starting_point()

def main():
    n, m, k = map(int, input().split())
    mn = m * n
    l = [_ == '.' for _ in range(n) for _ in input()]
    neigh = [[] for _ in range(mn)]
    for y in range(n - 1):
        for x in range(m):
            yx = y * m + x
            if l[yx] and l[yx + m]:
                neigh[yx].append(yx + m)
                neigh[yx + m].append(yx)
    for y in range(n):
        for x in range(m - 1):
            yx = y * m + x
            if l[yx] and l[yx + 1]:
                neigh[yx].append(yx + 1)
                neigh[yx + 1].append(yx)
    res = [True] * mn
    cur, nxt = set(), {l.index(True)}
    cnt = sum(l) - k
    while cnt:
        cur, nxt = nxt, cur
        while cur:
            i = cur.pop()
            if res[i]:
                res[i] = False
                cnt -= 1
                if not cnt:
                    break
                for j in neigh[i]:
                    if res[j]:
                        nxt.add(j)
    for x, (a, b) in enumerate(zip(res, l)):
        if a and b:
            l[x] = 2
    l = [''.join(('#', '.', 'X')[_] for _ in l[x:x + m]) for x in range(0, mn, m)]
    print('\n'.join(l))


def __starting_point():
    main()
__starting_point()

def main():
    n, m, k = map(int, input().split())
    mn = m * n
    l = [_ == '.' for _ in range(n) for _ in input()]
    neigh = [[] for _ in range(mn)]
    for y in range(n - 1):
        for x in range(m):
            yx = y * m + x
            if l[yx] and l[yx + m]:
                neigh[yx].append(yx + m)
                neigh[yx + m].append(yx)
    for y in range(n):
        for x in range(m - 1):
            yx = y * m + x
            if l[yx] and l[yx + 1]:
                neigh[yx].append(yx + 1)
                neigh[yx + 1].append(yx)
    res = [True] * mn
    cur, nxt = set(), {l.index(True)}
    cnt = sum(l) - k
    while cnt:
        cur, nxt = nxt, cur
        while cur:
            i = cur.pop()
            if res[i]:
                res[i] = False
                cnt -= 1
                if not cnt:
                    break
                for j in neigh[i]:
                    nxt.add(j)
    for x, (a, b) in enumerate(zip(res, l)):
        if a and b:
            l[x] = 2
    l = [''.join(('#', '.', 'X')[_] for _ in l[x:x + m]) for x in range(0, mn, m)]
    print('\n'.join(l))


def __starting_point():
    main()
__starting_point()

from queue import Queue, PriorityQueue
n, m, k = [int(x) for x in input().split()]
a = []
for i in range(n):
    a.append(list(input()))
lvl = [[0] * m for i in range(n)]
x = y = -1
for i in range(n):
    if '.' in a[i]:
        x = i
        y = a[i].index('.')
        break
q = Queue()
q.put((x, y))
ans = []
lvl[x][y] = 1
while not q.empty():
    x, y = q.get()
    for dx, dy in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
        nx = x + dx
        ny = y + dy
        if nx < 0 or ny < 0 or nx >= n or ny >= m:
            continue
        if lvl[nx][ny]:
            continue
        if a[nx][ny] == '#':
            continue
        lvl[nx][ny] = lvl[x][y] + 1
        q.put((nx, ny))
        ans.append((-lvl[nx][ny], nx, ny))
ans.sort()
for i in range(k):
    _, x, y = ans[i]
    a[x][y] = 'X'
print('\n'.join(''.join(l) for l in a))

# 377A
from sys import stdin

__author__ = 'artyom'


def read_int_ary():
  return map(int, stdin.readline().strip().split())


def dfs(graph, start):
  visited, tree, processed, stack = set(), [], set(), [start]
  while stack:
    vertex = stack.pop()
    if vertex not in visited:
      visited.add(vertex)
      stack.extend(graph[vertex] - visited)
    if not vertex in processed:
      tree.append(vertex)
    processed.add(vertex)
  return tree


n, m, k = read_int_ary()
grid = []
for i in range(n):
  grid.append(list(stdin.readline().strip()))

graph = {}
for i in range(n):
  for j in range(m):
    if grid[i][j] == '.':
      v = (i, j)
      graph[v] = set()
      if i > 0 and grid[i - 1][j] == '.':
        u = (i - 1, j)
        graph[v].add(u)
        graph[u].add(v)
      if j > 0 and grid[i][j - 1] == '.':
        u = (i, j - 1)
        graph[v].add(u)
        graph[u].add(v)

processed = dfs(graph, next(iter(graph.keys())))

added = set()
while len(added) < k:
  vertex = processed.pop()
  grid[vertex[0]][vertex[1]] = 'X'
  added.add(vertex)
for i in range(n):
  print(''.join(grid[i]))

# 377A
from sys import stdin

__author__ = 'artyom'


def read_int_ary():
  return map(int, stdin.readline().strip().split())


def dfs(graph, start):
  visited, tree, processed, stack = set(), [], set(), [start]
  while stack:
    vertex = stack.pop()
    if vertex not in visited:
      visited.add(vertex)
      stack.extend(graph[vertex] - visited)
    if not vertex in processed:
      tree.append(vertex)
    processed.add(vertex)
  return tree


n, m, k = read_int_ary()
grid = []
for i in range(n):
  grid.append(list(stdin.readline().strip()))

graph = {}
for i in range(n):
  for j in range(m):
    if grid[i][j] == '.':
      v = (i, j)
      graph[v] = set()
      if i > 0 and grid[i - 1][j] == '.':
        u = (i - 1, j)
        graph[v].add(u)
        graph[u].add(v)
      if j > 0 and grid[i][j - 1] == '.':
        u = (i, j - 1)
        graph[v].add(u)
        graph[u].add(v)

processed = dfs(graph, next(iter(graph.keys())))

i = 0
while i < k:
  vertex = processed.pop()
  grid[vertex[0]][vertex[1]] = 'X'
  i += 1
for i in range(n):
  print(''.join(grid[i]))

maze = [['0' for j in range(510)] for i in range(510)]
visited = [[0 for j in range(510)] for i in range(510)]
n,m,k = tuple(int(i) for i in input().split())
sx = -1
sy = -1
for i in range(n):
	s = input()
	for j in range(m):
		maze[i][j] = s[j]
		if(sx==-1 and s[j]=='.'):
			sx=i
			sy=j


stack = [(sx,sy)]
ans = []
while(len(stack)!=0):
	curr = stack.pop()
	x = curr[0]
	y = curr[1]
	#print(x,y)
	if(x<0 or y<0 or x>=n or y>=m or visited[x][y]==1 or maze[x][y]=='#'):
		continue
	visited[x][y] = 1
	stack.append((x+1,y))
	stack.append((x-1,y))
	stack.append((x,y+1))
	stack.append((x,y-1))
	ans.append(curr)

for i in range(k):
	curr = ans[len(ans)-i-1]
	x = curr[0]
	y = curr[1]
	maze[x][y] = 'X'
s = ""
for i in range(n):
	for j in range(m):
		s+=maze[i][j]
	s+="\n"
print(s)


from collections import deque,namedtuple
dx = [0,0,1,-1]
dy = [1,-1,0,0]

def main():
    n,m,limit = map(int,input().split())
    a,sx,sy,tot = [],0,0,0
    for i in range(n):
        s,t = input(),[]
        for j,c in enumerate(s):
            if c == '.':
                sx,sy = i,j
                tot += 1
                c = 'X'
            t.append(c)
        a.append(t[:])

    dq,done = deque([(sx,sy)]),0
    while len(dq) > 0:
        now = dq.pop()
        if done >= tot - limit:
            break
        if(a[now[0]][now[1]] == 'X'):
            done += 1
        a[now[0]][now[1]] = '.'
        for i in range(4):
            tx,ty = dx[i] + now[0],dy[i] + now[1]
            if 0 <= tx < n and 0 <= ty < m and a[tx][ty] == 'X':
                dq.append((tx,ty))
    for i in a:
        print("".join(i))



def __starting_point():
    main()
__starting_point()

from collections import deque,namedtuple
dx = [0,0,1,-1]
dy = [1,-1,0,0]

def main():
    n,m,limit = map(int,input().split())
    a,sx,sy,tot = [],0,0,0
    for i in range(n):
        s,t = input(),[]
        for j,c in enumerate(s):
            if c == '.':
                sx,sy = i,j
                tot += 1
                c = 'X'
            t.append(c)
        a.append(t[:])

    dq,done = deque([(sx,sy)]),0
    while len(dq) > 0:
        now = dq.pop()
        if done >= tot - limit:
            break
        if(a[now[0]][now[1]] == 'X'):
            done += 1
        else:
            continue
        a[now[0]][now[1]] = '.'
        for i in range(4):
            tx,ty = dx[i] + now[0],dy[i] + now[1]
            if 0 <= tx < n and 0 <= ty < m and a[tx][ty] == 'X':
                dq.append((tx,ty))
    for i in a:
        print("".join(i))



def __starting_point():
    main()
__starting_point()

from collections import deque,namedtuple
dx = [0,0,1,-1]
dy = [1,-1,0,0]

def main():
    n,m,limit = map(int,input().split())
    a,sx,sy,tot = [],0,0,0
    for i in range(n):
        s,t = input(),[]
        for j,c in enumerate(s):
            if c == '.':
                sx,sy = i,j
                tot += 1
                c = 'X'
            t.append(c)
        a.append(t[:])

    dq,done = deque([(sx,sy)]),0
    while len(dq) > 0:
        now = dq.popleft()
        if done >= tot - limit:
            break
        if(a[now[0]][now[1]] == 'X'):
            done += 1
        else:
            continue
        a[now[0]][now[1]] = '.'
        for i in range(4):
            tx,ty = dx[i] + now[0],dy[i] + now[1]
            if 0 <= tx < n and 0 <= ty < m and a[tx][ty] == 'X':
                dq.append((tx,ty))
    for i in a:
        print("".join(i))



def __starting_point():
    main()
__starting_point()

import sys

def solve(n, m, k, grid, r, c):
    move = [(0, 1), (0, -1), (1, 0), (-1, 0)]
    visited = [[False for i in range(m)] for j in range(n)]
    q = [(r, c)]
    grid[r][c] = 'O'
    visited[r][c] = True
    k -= 1
    while k != 0 and len(q) != 0:
        r, c = q.pop()
        for i in range(4):
            x, y = r + move[i][0], c + move[i][1]
            if x >= 0 and x < n and y >= 0 and y < m and not visited[x][y] and grid[x][y] == '.':
                q.append((x, y))
                grid[x][y] = 'O'
                visited[x][y] = True
                k -= 1
                if k == 0:
                    break

n, m, k = list(map(int, sys.stdin.readline().split()))
grid = []
for i in range(n):
    s = list(input())
    grid.append(s)

r = 0
c = 0
cnt = 0
find = False
for i in range(n):
    for j in range(m):
        if grid[i][j] == '.':
            cnt += 1
            if not find:
                r, c = i, j
                find = True

solve(n, m, cnt-k, grid, r, c)

for i in range(n):
    for j in range(m):
        if grid[i][j] == '.':
            grid[i][j] = 'X'
#print(grid)

for i in range(n):
    for j in range(m):
        if grid[i][j] == 'O':
            grid[i][j] = '.'

for i in range(n):
    print(''.join(map(str, grid[i])))



from typing import List, Tuple, Set


def find_neighbors(x: int, y: int, m: int, n: int) -> List[Tuple[int, int]]:
    neighbors = [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]
    return [p for p in neighbors if 0 <= p[0] < n and 0 <= p[1] < m]


def dfs(
    n: int,
    m: int,
    maze: List[List[str]],
    start: Tuple[int, int],
    max_path_length: int,
) -> Set[Tuple[int, int]]:
    visited = [[0] * m for _ in range(n)]
    d = [start]
    path = set()
    while d:
        x, y = d.pop()
        visited[x][y] = 1
        path.add((x, y))
        for xo, yo in find_neighbors(x, y, m, n):
            if not visited[xo][yo] and maze[xo][yo] == '.':
                d.append((xo, yo))
        if len(path) == max_path_length:
            break
    return path


def place_blocks(
    n: int,
    m: int,
    k: int,
    maze: List[List[str]],
    path: Set[Tuple[int, int]]
) -> List[List[str]]:
    for i in range(n):
        for j in range(m):
            if maze[i][j] == '.' and k > 0 and (i, j) not in path:
                maze[i][j] = 'X'
                k -= 1
            if k == 0:
                return maze


def solve(n: int, m: int, k: int, maze: List[List[str]]) -> List[List[str]]:
    empty_cell_count = sum(row.count('.') for row in maze)
    for i in range(n):
        for j in range(m):
            if maze[i][j] != '#':
                path = dfs(n, m, maze, (i, j), empty_cell_count - k)
                if len(path) >= empty_cell_count - k:
                    return place_blocks(n, m, k, maze, path)

n, m, k = list(map(int, input().split()))
maze = [list(input()) for _ in range(n)]

for line in solve(n, m, k, maze):
    print(''.join(line))

from sys import stdin
from collections import deque

def __starting_point():
    R, C, K = list(map(int, stdin.readline().rstrip().split()))
    maze = []
    start = None
    for r in range(0, R):
        line = stdin.readline()
        if start is None:
            for c in range(0, C):
                if line[c] == '.':
                    start = (r, c)
                    break
        maze.append(list(line))

    order = deque()
    stack = deque()
    stack.append(start)

    def add_to_stack(row, col):
        if 0 <= row < R and \
                0 <= col < C and \
                maze[row][col] == '.':
            stack.append((row, col))
            maze[row][col] = ','

    while len(stack) > 0:
        (r, c) = stack.pop()
        order.append((r, c))
        add_to_stack(r-1, c)
        add_to_stack(r+1, c)
        add_to_stack(r, c-1)
        add_to_stack(r, c+1)

    for k in range(0, K):
        (r, c) = order.pop()
        maze[r][c] = 'X'

    for r in range(0, R):
        line = ''
        for c in range(0, C):
            ch = maze[r][c]
            if ch == ',':
                line += '.'
            else:
                line += ch
        print(line)


__starting_point()

n,m,k=list(map(int,input().split()))
M=[input() for i in range(n)]
T=[[] for i in range(n)]
p=0
for i in range(n) :
    for j in range(m) :
        if M[i][j]=='#' :
            T[i].append(M[i][j])
        else :
            T[i].append('X')
for i in range(n) :
    p=p+M[i].count('#')
for i in range(n) :
    for j in range(m) :
        if M[i][j]=='.' :
            a=i
            b=j
            break
t=(n*m)-p-k
l=[[a,b]]
T[a][b]='.'
t=t-1
while t>0  :
    r=l[0]
    
    del(l[0])
    i=r[0]
    j=r[1]
  
    if i+1!=n  :
        if M[i+1][j]=='.' and T[i+1][j]!='.'  :
            l.append([i+1,j])
            T[i+1][j]='.'
            t=t-1
    if t<=0 :
        break
    if i-1!=-1  :
        if M[i-1][j]=='.' and T[i-1][j]!='.'  :
            l.append([i-1,j])
            T[i-1][j]='.'
            t=t-1
    if t<=0 :
        break
    if j+1!=m  :
        if M[i][j+1]=='.' and  T[i][j+1]!='.'  :
            l.append([i,j+1])
            T[i][j+1]='.'
            t=t-1
    if t<=0 :
        break
    if j-1!=-1  :
        if M[i][j-1]=='.' and  T[i][j-1]!='.' :
            l.append([i,j-1])
            T[i][j-1]='.'
            t=t-1
            
for i in range(n) :
    S=''
    for j in range(m) :
        S=S+T[i][j]
    print(S)


#make every dot into X,turn the question into find a connected line of dot
#scan the graph and find the first X's position in every line,and to each X find if there is another
#X near it ,take it in and do it again
n,m,k = map(int,input().split())
g = [input().replace('.','X') for i in range(n)]
k = n*m - k - sum(i.count('#')for i in g)
g = [list(i) for i in g]
i,p = 0,[]
while k:
    if 'X'in g[i]:
        j = g[i].index('X')
        g[i][j],p = '.',[(i,j)]
        k -= 1
        break
    i += 1
while k:
    x,y = p.pop()
    for i,j in ((x,y-1),(x,y+1),(x-1,y),(x+1,y)):
        if i < 0 or j < 0:
            continue
        if i < n and j < m and g[i][j] == 'X':
            g[i][j] = '.'
            p.append((i,j))
            k -= 1
            if k == 0:
                break
for i in range(n):
    g[i]=''.join(g[i])
print('\n'.join(g))

import sys
from collections import defaultdict

def main():
    sys.setrecursionlimit(1 << 30)
    g = []
    adj = defaultdict(set)
    vis = set()
    def valid(x, y):
        nonlocal n, m
        return x >= 0 and x < n and y >= 0 and y < m
    def bfs(x, y):
        nonlocal g, vis, adj
        q = []
        q.append((x, y))
        vis.add((x, y))
        s = 0
        while len(q) > 0:
            (x, y) = q.pop()
            s += 1
            for c in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
                nx = c[0] + x
                ny = c[1] + y
                if valid(nx, ny) and (nx, ny) not in vis:
                    if g[nx][ny] == '.':
                        vis.add((nx, ny))
                        q.append((nx, ny))
        return s
    def bfs2(x, y):
        nonlocal g, vis, adj, count
        q = []
        q.append((x, y))
        vis.add((x, y))
        while len(q) > 0:
            (x, y) = q.pop()
            g[x][y] = 'o'
            count -= 1
            if count <= 0:
                return
            for c in [[-1, 0], [1, 0], [0, -1], [0, 1]]:
                nx = c[0] + x
                ny = c[1] + y
                if valid(nx, ny) and (nx, ny) not in vis:
                    if g[nx][ny] == '.':
                        vis.add((nx, ny))
                        q.append((nx, ny))
    (n, m, k) = list(map(int, input().split(' ')))
    for i in range(n):
        g.append(list(input()))
    s = 0
    f = False
    l = None
    for i in range(n):
        if f:
            break
        for j in range(m):
            if g[i][j] == '.' and (i, j) not in vis:
                s = bfs(i, j)
                l = (i, j)
                f = True
                break
    vis = set()
    count = s - k
    bfs2(l[0], l[1])
    f = lambda i: 'X' if i == '.' else ('#' if i == '#' else '.')
    for row in g:
        print(''.join(list(map(f, row))))
main()



from collections import deque as dq

class Graph:
    def __init__(self,n=0,m=0):
        self.g=[None for i in range(n)]
        self.vis=[[False for j in range(m)] for i in range(n)]
        self.dx=(1,0,-1,0)
        self.dy=(0,1,0,-1)

    def affiche(self):
        for i in range(len(self.g)):
            print("".join(self.g[i]))
    def readG(self,n):
        for i in range(n):
            self.g[i]=list(input())

    def get(self,i,j):
        return self.g[i][j]
            
    def dfsIt(self,u):
        nonlocal k,A
        L=dq()
        A=[]
        L.append(u)        
        while len(L)!=0:
            u=L.pop()
            self.vis[u[0]][u[1]]=True
            b=True
            for t in range(4):
                x=u[0]+self.dx[t]
                y=u[1]+self.dy[t]
                if x>=0 and x<n and y>=0 and y<m and not self.vis[x][y] and self.g[x][y]!='#':
                    self.vis[x][y]=True
                    L.append((x,y))
                    b=False
            if b and k>0:
                k-=1
                self.g[u[0]][u[1]]='X'
            else:
                A.append(u)
    
n,m,k=list(map(int,input().split()))
g=Graph(n,m)
g.readG(n)

def f():
    nonlocal n,m,g
    for i in range(n):
        for j in range(m):
            if g.get(i,j)=='.':
                return (i,j)
            
g.dfsIt(f())
while k!=0:
    k-=1
    u=A.pop()
    g.g[u[0]][u[1]]='X'

g.affiche()
    


r,c,n = map(int,input().split())
field = []
field.append('#'*(c+2))
for _ in range(r):
    field.append('#'+input()+'#')
field.append('#'*(c+2))


p_x = 0
p_y = 0


not_walls = 0
for x in range(1,r+1):
    for y in range(1,c+1):
        if field[x][y] == '#':continue
        p_x,p_y = x,y
        not_walls += 1
process = [(p_x,p_y)]
valid = set()

while len(valid) < (not_walls-n):
    x,y = process.pop()
    valid.add((x,y))

    for a,b in [(1,0),(-1,0),(0,1),(0,-1)]:
        if field[a+x][b+y] == '.' and (a+x,b+y) not in valid:
            process.append((x+a,y+b))



for x in range(1,r+1):
    for y in range(1,c+1):
        if field[x][y] == '#':continue
        if (x,y) not in valid:
            field[x] = field[x][:y] + 'X' + field[x][y+1:]

field = [x[1:-1] for x in field[1:-1]]
print('\n'.join(field))

n, m, k = list(map(int, input().split()))
maze = [["#"]*(m+2)]+[list("#"+input()+"#") for i in range(n)]+[["#"]*(m+2)]
steps = [[0,1],[0,-1],[1,0],[-1,0]]

empty = -k
x, y = None, None
for i in range(n+2):
    empty += maze[i].count(".")
    for j in range(m+2):
        if maze[i][j] == ".":
            x, y = i, j
            break

stack = [(x,y)]
while empty:
    (x, y) = stack.pop()
    if maze[x][y] == "v":
        continue
    for dx, dy in steps:
        if maze[x+dx][y+dy] == ".":
            stack.append((x+dx, y+dy))
    maze[x][y] = "v"
    empty -= 1

for row in maze[1:-1]:
    print("".join(row[1:-1]).replace(".","X").replace("v","."))