AtCoder Grand Contest 004 - AND Grid

Snuke and Ciel went to a strange stationery store. Each of them got a transparent graph paper with H rows and W columns.

Snuke painted some of the cells red in his paper. Here, the cells painted red were 4-connected, that is, it was possible to traverse from any red cell to any other red cell, by moving to vertically or horizontally adjacent red cells only.

Ciel painted some of the cells blue in her paper. Here, the cells painted blue were 4-connected.

Afterwards, they precisely overlaid the two sheets in the same direction. Then, the intersection of the red cells and the blue cells appeared purple.

You are given a matrix of letters a_{ij} (1≤i≤H, 1≤j≤W) that describes the positions of the purple cells. If the cell at the i-th row and j-th column is purple, then a_{ij} is `#`, otherwise a_{ij} is `.`. Here, it is guaranteed that no outermost cell is purple. That is, if i=1, H or j = 1, W, then a_{ij} is `.`.

Find a pair of the set of the positions of the red cells and the blue cells that is consistent with the situation described. It can be shown that a solution always exists.

Constraints

* 3≤H,W≤500
* a_{ij} is `#` or `.`.
* If i=1,H or j=1,W, then a_{ij} is `.`.
* At least one of a_{ij} is `#`.

Input

The input is given from Standard Input in the following format:


H W
a_{11}...a_{1W}
:
a_{H1}...a_{HW}


Output

Print a pair of the set of the positions of the red cells and the blue cells that is consistent with the situation, as follows:

* The first H lines should describe the positions of the red cells.
* The following 1 line should be empty.
* The following H lines should describe the positions of the blue cells.



The description of the positions of the red or blue cells should follow the format of the description of the positions of the purple cells.

Examples

Input

5 5
.....
.#.#.
.....
.#.#.
.....


Output

.....
#####
#....
#####
.....

.###.
.#.#.
.#.#.
.#.#.
.....


Input

7 13
.............
.###.###.###.
.#.#.#...#...
.###.#...#...
.#.#.#.#.#...
.#.#.###.###.
.............


Output

.............
.###########.
.###.###.###.
.###.###.###.
.###.###.###.
.###.###.###.
.............

.............
.###.###.###.
.#.#.#...#...
.###.#...#...
.#.#.#.#.#...
.#.#########.
.............

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
(h, w) = map(int, input().split())
ans1 = [['.'] * w for _ in range(h)]
ans2 = [['.'] * w for _ in range(h)]
for i in range(h):
	ans1[i][0] = '#'
	ans2[i][-1] = '#'
	if i % 2:
		for j in range(w - 1):
			ans1[i][j] = '#'
	else:
		for j in range(1, w):
			ans2[i][j] = '#'
for i in range(h):
	s = input()
	for j in range(w):
		if s[j] == '#':
			ans1[i][j] = '#'
			ans2[i][j] = '#'
for row in ans1:
	print(''.join(row))
print()
for row in ans2:
	print(''.join(row))


(h, w) = (int(x) for x in input().split())
A = [list(input()) for _ in range(h)]
R = [['.'] * w for _ in range(h)]
B = [['.'] * w for _ in range(h)]
for i in range(h):
	for j in range(w):
		if 0 < i < h - 1 and 0 < j < w - 1:
			if i % 2 == 1 or (i % 4 == 2 and j == w - 2) or (i % 4 == 0 and j == 1):
				R[i][j] = '#'
		if R[i][j] != '#':
			B[i][j] = '#'
for i in range(h):
	for j in range(w):
		if A[i][j] == '#':
			R[i][j] = '#'
			B[i][j] = '#'
for r in R:
	print(''.join(r))
print()
for b in B:
	print(''.join(b))


(H, W) = map(int, input().split())
a = [list(input()) for i in range(H)]
b = [['.' for i in range(W)] for i in range(H)]
c = [['.' for i in range(W)] for i in range(H)]
for i in range(H):
	c[i][0] = '#'
	b[i][-1] = '#'
for i in range(H):
	for j in range(W):
		if i % 2 == 0:
			b[i][j] = '#'
		else:
			c[i][j] = '#'
for i in range(H):
	c[i][-1] = '.'
	b[i][0] = '.'
for i in range(H):
	for j in range(W):
		if a[i][j] == '#':
			b[i][j] = '#'
			c[i][j] = '#'
for i in b:
	print(''.join(i))
print()
for i in c:
	print(''.join(i))


(H, W) = list(map(int, input().split()))
a = [input() for i in range(H)]
b = [[] for i in range(H)]
r = [[] for i in range(H)]
for i in range(H):
	for j in range(W):
		if i == 0:
			b[i].append('#')
			r[i].append('.')
		elif i == H - 1:
			b[i].append('.')
			r[i].append('#')
		elif a[i][j] == '#':
			b[i].append('#')
			r[i].append('#')
		elif j % 2 == 0:
			b[i].append('.')
			r[i].append('#')
		elif j % 2 == 1:
			b[i].append('#')
			r[i].append('.')
for i in range(H):
	ans = ''
	for j in range(W):
		ans = ans + b[i][j]
	print(ans)
print('')
for i in range(H):
	ans = ''
	for j in range(W):
		ans = ans + r[i][j]
	print(ans)


import math, string, itertools, fractions, heapq, collections, re, array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10 ** 7)
inf = 10 ** 20
eps = 1.0 / 10 ** 10
mod = 10 ** 9 + 7

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def LI_():
	return [int(x) - 1 for x in sys.stdin.readline().split()]

def LF():
	return [float(x) for x in sys.stdin.readline().split()]

def LS():
	return sys.stdin.readline().split()

def I():
	return int(sys.stdin.readline())

def F():
	return float(sys.stdin.readline())

def S():
	return input()

def main():
	(h, w) = LI()
	a = [[c == '#' for c in S()] for _ in range(h)]
	r = ['#' * w]
	for c in a[1:-1]:
		t = ''
		for i in range(w):
			ci = c[i]
			if ci or i % 2 == 0:
				t += '#'
			else:
				t += '.'
		r.append(t)
	r.append('.' * w)
	r.append('')
	r.append('.' * w)
	for c in a[1:-1]:
		t = ''
		for i in range(w):
			ci = c[i]
			if ci or i % 2 == 1:
				t += '#'
			else:
				t += '.'
		r.append(t)
	r.append('#' * w)
	return '\n'.join(r)
print(main())


(H, W) = map(int, input().split())
A = []
for _ in range(H):
	A.append(input())
(x, y) = ([], [])
for (i, a) in enumerate(A):
	if i % 2:
		y.append('#' + a[1:])
		x.append('.' + '#' * (W - 1))
	else:
		x.append(a[:-1] + '#')
		y.append('#' * (W - 1) + '.')
print(*x, sep='\n')
print('')
print(*y, sep='\n')


(H, W) = map(int, input().split())
Ass = [input() for _ in range(H)]
redss = [['#'] + ['.'] * (W - 1) for _ in range(H)]
bluess = [['.'] * (W - 1) + ['#'] for _ in range(H)]
for i in range(H):
	if i % 2:
		redss[i] = ['#'] * (W - 1) + ['.']
	else:
		bluess[i] = ['.'] + ['#'] * (W - 1)
for i in range(H):
	for j in range(W):
		if Ass[i][j] == '#':
			redss[i][j] = '#'
			bluess[i][j] = '#'
print('\n'.join(map(''.join, redss)))
print()
print('\n'.join(map(''.join, bluess)))


import itertools
import random

def genrandom(h, w):
	g = [[0] * w for _ in range(h)]
	for i in range(1, h - 1):
		for j in range(1, w - 1):
			if random.randint(0, 1):
				g[i][j] = 1
	return g

def display(g):
	for i in range(len(g)):
		print(''.join(('#' if b else '.' for b in g[i])))
(h, w) = [int(s) for s in input().split()]
g = [[0] * w for _ in range(h)]
for i in range(h):
	s = input()
	for (j, c) in enumerate(s):
		if c == '#':
			g[i][j] = 1
red = [list(g[i]) for i in range(h)]
blue = [list(g[i]) for i in range(h)]
for i in range(h):
	red[i][-1] = 1
	blue[i][0] = 1
	if i % 2 == 0:
		for j in range(1, w - 1):
			red[i][j] = 1
	else:
		for j in range(1, w - 1):
			blue[i][j] = 1
display(red)
print()
display(blue)


import sys
input = sys.stdin.readline
(H, W) = map(int, input().split())
state = [list(input().rstrip()) for _ in range(H)]
ans = [[['.'] * W for _ in range(H)] for _ in range(2)]
color = 0
was_blank = False
for h in range(H):
	must_color = []
	for w in range(W):
		if state[h][w] == '#':
			must_color.append(w)
	if not must_color:
		if not was_blank:
			color ^= 1
		for w in range(1, W):
			ans[color][h][w] = '#'
		ans[color ^ 1][h][0] = '#'
		was_blank = True
	else:
		color ^= 1
		for w in range(W):
			ans[color][h][w] = '#'
		for w in must_color:
			ans[color ^ 1][h][w] = '#'
		was_blank = False
for h in range(H):
	print(''.join(ans[0][h]))
print()
for h in range(H):
	print(''.join(ans[1][h]))


(h, w) = map(int, input().split())
a = [list(input()) for i in range(h)]
ta = [['.'] * w for i in range(h)]
ao = [['.'] * w for i in range(h)]
for i in range(h):
	if i % 2 == 0:
		for j in range(w - 1):
			ta[i][j] = '#'
		ao[i][-1] = '#'
	else:
		for j in range(1, w):
			ao[i][j] = '#'
		ta[i][0] = '#'
for i in range(h):
	for j in range(w):
		if a[i][j] == '#':
			ta[i][j] = '#'
			ao[i][j] = '#'
for i in range(h):
	print(*ta[i], sep='')
print()
for i in range(h):
	print(*ao[i], sep='')


(H, W) = map(int, input().split())
a = [[s for s in input()] for i in range(H)]

def make_red_map():
	red_map = [row[:] for row in a]
	for i in range(0, H, 2):
		for j in range(W - 1):
			if red_map[i][j] == '.':
				red_map[i][j] = '#'
	for i in range(H):
		red_map[i][0] = '#'
	for i in range(H):
		for j in range(W):
			print(red_map[i][j], end='')
		print()

def make_blue_map():
	blue_map = [row[:] for row in a]
	for i in range(1, H, 2):
		for j in range(1, W):
			if blue_map[i][j] == '.':
				blue_map[i][j] = '#'
	for i in range(H):
		blue_map[i][W - 1] = '#'
	for i in range(H):
		for j in range(W):
			print(blue_map[i][j], end='')
		print()
make_red_map()
print()
make_blue_map()


(H, W) = map(int, input().split())
a = []
for i in range(H):
	A = list(input())
	a.append(A)
ans1 = [['.'] * W for i in range(H)]
ans2 = [['.'] * W for i in range(H)]
for i in range(H):
	for j in range(W):
		if i == 0:
			ans1[i][j] = '#'
			continue
		if i == H - 1:
			ans2[i][j] = '#'
			continue
		if a[i][j] == '#':
			ans1[i][j] = '#'
			ans2[i][j] = '#'
		elif j % 2 == 0:
			ans1[i][j] = '#'
		else:
			ans2[i][j] = '#'
for i in ans1:
	print(''.join(i))
print('')
for i in ans2:
	print(''.join(i))


(h, w) = map(int, input().split())
arr = []
exist = []
for i in range(h):
	s = input()
	a = []
	f = 0
	for j in range(w):
		if s[j] == '#':
			a.append(1)
			f = 1
		else:
			a.append(0)
	arr.append(a)
	if f == 1:
		exist.append(1)
	else:
		exist.append(0)
red = [[0 for i in range(w)] for j in range(h)]
blue = [[0 for i in range(w)] for j in range(h)]
flag = 0
pre_non_exist = 0
for i in range(h):
	if i == 0:
		for j in range(w):
			red[i][j] = 1
		flag = 1
	elif exist[i] == 1 and flag == 1:
		pre_non_exist = 0
		for j in range(w):
			blue[i][j] = 1
			if arr[i][j] == 1:
				red[i][j] = 1
		flag = 0
	elif exist[i] == 1 and flag == 0:
		pre_non_exist = 0
		for j in range(w):
			red[i][j] = 1
			if arr[i][j] == 1:
				blue[i][j] = 1
		flag = 1
	else:
		if pre_non_exist == 0:
			flag = (flag + 1) % 2
		pre_non_exist = 1
		if flag == 0:
			for j in range(w):
				if j == 0 or j == w - 1:
					red[i][j] = 1
				else:
					blue[i][j] = 1
		else:
			for j in range(w):
				if j == 0 or j == w - 1:
					blue[i][j] = 1
				else:
					red[i][j] = 1
for i in range(h):
	s = ''
	for j in range(w):
		if red[i][j] == 1:
			s = s + '#'
		else:
			s = s + '.'
	print(s)
print()
for i in range(h):
	s = ''
	for j in range(w):
		if blue[i][j] == 1:
			s = s + '#'
		else:
			s = s + '.'
	print(s)


import copy
(h, w) = map(int, input().split())
f = [list(input()) for _ in range(h)]
a = copy.deepcopy(f)
b = copy.deepcopy(f)
a[0] = '#' * w
for y in range(1, h - 1):
	for x in range(w):
		[a, b][x % 2][y][x] = '#'
b[h - 1] = '#' * w
print(*map(''.join, a), sep='\n')
print()
print(*map(''.join, b), sep='\n')


INF = float('inf')

def inpl():
	return list(map(int, input().split()))
(H, W) = inpl()
X = [list(input()) for _ in range(H)]
A = [['.' for _ in range(W)] for _ in range(H)]
B = [['.' for _ in range(W)] for _ in range(H)]
tmp = ['#' for _ in range(W - 1)]
for i in range(H):
	if i % 2 == 0:
		A[i][:-1] = tmp
		B[i][-1] = '#'
	else:
		B[i][1:] = tmp
		A[i][0] = '#'
for h in range(H):
	for w in range(W):
		if X[h][w] == '#':
			A[h][w] = '#'
			B[h][w] = '#'
for a in A:
	print(''.join(a))
print('')
for b in B:
	print(''.join(b))


(H, W) = map(int, input().split())
lines = [input() for _ in range(H)]
rs = [list('#' + (W - 2) * ('#' if i % 2 == 0 else '.') + '.') for i in range(H)]
bs = [list('.' + (W - 2) * ('#' if i % 2 == 1 else '.') + '#') for i in range(H)]
for (i, line) in enumerate(lines):
	for (j, c) in enumerate(line):
		if c == '#':
			rs[i][j] = '#'
			bs[i][j] = '#'
print('\n'.join([''.join(r) for r in rs]), end='\n' * 2)
print('\n'.join([''.join(b) for b in bs]), end='\n' * 2)


def main():
	import sys
	input = sys.stdin.readline
	(H, W) = map(int, input().split())
	grid_p = []
	for _ in range(H):
		grid_p.append(input().rstrip('\n'))
	grid_r = [['.'] * W for _ in range(H)]
	grid_b = [['.'] * W for _ in range(H)]
	for w in range(W):
		grid_r[0][w] = '#'
		grid_b[-1][w] = '#'
	for h in range(1, H - 1):
		for w in range(W):
			if w % 2:
				grid_r[h][w] = '#'
			else:
				grid_b[h][w] = '#'
	for h in range(H):
		for w in range(W):
			if grid_p[h][w] == '#':
				grid_r[h][w] = '#'
				grid_b[h][w] = '#'
	[print(''.join(line)) for line in grid_r]
	print('')
	[print(''.join(line)) for line in grid_b]
main()


readline = open(0).readline
writelines = open(1, 'w').writelines
(H, W) = map(int, readline().split())
S = []
T = []
for i in range(H):
	for (j, a) in enumerate(readline().strip()):
		if a == '#':
			S.append('#')
			T.append('#')
		elif j == 0:
			S.append('#')
			T.append('.')
		elif j == W - 1:
			S.append('.')
			T.append('#')
		elif i % 2 == 0:
			S.append('#')
			T.append('.')
		else:
			S.append('.')
			T.append('#')
	S.append('\n')
	T.append('\n')
S.append('\n')
writelines(S)
writelines(T)


from collections import defaultdict, Counter
from itertools import product, groupby, count, permutations, combinations
from math import pi, sqrt
from collections import deque
from bisect import bisect, bisect_left, bisect_right
INF = 10 ** 10

def check(ans1, ans2, field):
	(h, w) = (len(ans1), len(ans1[0]))
	ans = [[0] * w for _ in range(h)]
	for y in range(h):
		for x in range(w):
			c = '#' if ans1[y][x] == ans2[y][x] == '#' else '.'
			if field[y][x] != c:
				print(y, x)

def main():
	(H, W) = map(int, input().split())
	field = []
	for _ in range(H):
		field.append(input())
	(ans1, ans2) = ([['.'] * W for _ in range(H)], [['.'] * W for _ in range(H)])
	for i in range(H):
		ans1[i][0] = '#'
		ans2[i][-1] = '#'
		if i % 2 == 0:
			ans1[i] = ['#'] * (W - 1) + ['.']
		else:
			ans2[i] = ['.'] + ['#'] * (W - 1)
	for y in range(H):
		for x in range(W):
			if field[y][x] == '#':
				if y % 2 == 0:
					ans2[y][x] = '#'
				else:
					ans1[y][x] = '#'
	for line in ans1:
		print(''.join(line))
	print()
	for line in ans2:
		print(''.join(line))
main()


import sys
input = sys.stdin.readline
import copy
from collections import deque
(H, W) = map(int, input().split())
A = [[0] * W for i in range(H)]
for i in range(H):
	S = input()
	for j in range(W):
		A[i][j] = S[j]
C = copy.deepcopy(A)
for h in range(W):
	C[0][h] = '#'
for j in range(W):
	if j % 2 == 1:
		for i in range(H - 1):
			C[i][j] = '#'
D = copy.deepcopy(A)
for h in range(W):
	D[-1][h] = '#'
for j in range(W):
	if j % 2 == 0:
		for i in range(1, H):
			D[i][j] = '#'
for i in range(H):
	print(''.join(C[i]))
print()
for i in range(H):
	print(''.join(D[i]))


(ae, be) = ('', '')
(h, w) = map(int, input().split())
a = [['#' for i in range(w)] for _ in range(h)]
b = [['#' for i in range(w)] for _ in range(h)]
a[-1] = ['.' for i in range(w)]
b[0] = ['.' for i in range(w)]
if w % 2 == 1:
	ae = '#'
	be = '.'
for i in range(1, h - 1):
	(x, y) = ('#', '.')
	for j in range(w):
		a[i][j] = x
		b[i][j] = y
		(x, y) = (y, x)
for i in range(h):
	s = input()
	for j in range(w):
		if s[j] == '#':
			a[i][j] = '#'
			b[i][j] = '#'
for i in range(h):
	print(''.join(a[i]))
print('')
for i in range(h):
	print(''.join(b[i]))


from __future__ import division, print_function, absolute_import, unicode_literals
(H, W) = map(int, input().split())
RED = ['' for _ in range(H)]
BLUE = ['' for _ in range(H)]
for y in range(H):
	s = input()
	RED[y] = s
	BLUE[y] = s
RED[0] = '#' * W
BLUE[-1] = '#' * W
for y in range(0, H - 1):
	tmp = ''
	for x in range(0, W):
		if RED[y][x] == '#' or x % 2 == 0:
			tmp += '#'
		else:
			tmp += '.'
	RED[y] = tmp
for y in range(1, H - 1):
	tmp = ''
	for x in range(0, W):
		if BLUE[y][x] == '#' or x % 2 != 0:
			tmp += '#'
		else:
			tmp += '.'
	BLUE[y] = tmp
for w in RED:
	print(w)
print()
for w in BLUE:
	print(w)


def main():
	(H, W) = map(int, input().split())
	A = [input() for _ in range(H)]
	ansr = [None for _ in range(H)]
	ansb = [None for _ in range(H)]
	for i in range(0, H):
		if i % 2 == 0:
			ansr[i] = ['#'] * (W - 1) + ['.']
			ansb[i] = ['.'] * (W - 1) + ['#']
		else:
			ansr[i] = ['#'] + ['.'] * (W - 1)
			ansb[i] = ['.'] + ['#'] * (W - 1)
	for i in range(H):
		for j in range(W):
			if A[i][j] == '#':
				ansr[i][j] = '#'
				ansb[i][j] = '#'
	for i in range(H):
		print(''.join(ansr[i]))
	print()
	for i in range(H):
		print(''.join(ansb[i]))
main()


from collections import defaultdict
con = 10 ** 9 + 7
INF = float('inf')

def getlist():
	return list(map(int, input().split()))

def main():
	(H, W) = getlist()
	L = []
	for i in range(H):
		l = list(input())
		L.append(l)
	redTable = [['.'] * W for i in range(H)]
	blueTable = [['.'] * W for i in range(H)]
	for i in range(H):
		redTable[i][0] = '#'
		blueTable[i][-1] = '#'
	for i in range(H):
		if i % 2 == 0:
			for j in range(1, W - 1):
				redTable[i][j] = '#'
		else:
			for j in range(1, W - 1):
				blueTable[i][j] = '#'
	for i in range(H):
		for j in range(1, W - 1):
			if L[i][j] == '#':
				if i % 2 == 0:
					blueTable[i][j] = '#'
				else:
					redTable[i][j] = '#'
	for i in range(H):
		print(''.join(redTable[i]))
	print()
	for i in range(H):
		print(''.join(blueTable[i]))
main()


(H, W) = map(int, input().split())
V = [input() for _ in range(H)]
B = ['' for _ in range(H)]
R = ['' for _ in range(H)]
N = '#' * (W - 1)
for i in range(H):
	if i % 2 == 0:
		B[i] = N + V[i][-1]
		R[i] = V[i][:W - 1] + '#'
	else:
		R[i] = V[i][-1] + N
		B[i] = '#' + V[i][1:]
for i in range(H):
	print(B[i])
print('')
for i in range(H):
	print(R[i])


(H, W) = map(int, input().split())
blue = [[0] * W for _ in range(H)]
red = [[0] * W for _ in range(H)]
for x in range(W):
	blue[0][x] = 1
	red[-1][x] = 1
for y in range(H - 1):
	for x in range(0, W, 2):
		blue[y][x] = 1
		if x + 1 < W:
			red[y + 1][x + 1] = 1
m = [input() for _ in range(H)]
for color in [red, blue]:
	for y in range(H):
		for x in range(W):
			if m[y][x] == '#':
				print('#', end='')
			elif color[y][x] == 1:
				print('#', end='')
			else:
				print('.', end='')
		print()
	print()


(h, w) = map(int, input().split())
grid = [list(input()) for i in range(h)]
black = [[1 for i in range(w)] for j in range(h)]
white = [[1 for i in range(w)] for j in range(h)]
for i in range(h):
	for j in range(w):
		if i % 2 and j % 2 == 0:
			black[i][j] = 0
		elif i % 2 == 0 and j % 2:
			white[i][j] = 0
for i in range(h):
	for j in range(w):
		if grid[i][j] == '#':
			black[i][j] = 1
			white[i][j] = 1
		elif i % 2 == 0:
			white[i][j] = 0
		else:
			black[i][j] = 0
for i in range(h):
	black[i][0] = 0
	black[i][w - 1] = 1
	white[i][0] = 1
	white[i][w - 1] = 0
for i in range(w):
	black[0][i] = 1
	black[h - 1][i] = 0
	white[0][i] = 0
	white[h - 1][i] = 1
for i in range(h):
	for j in range(w):
		if black[i][j]:
			print('#', end='')
		else:
			print('.', end='')
	print()
print()
for i in range(h):
	for j in range(w):
		if white[i][j]:
			print('#', end='')
		else:
			print('.', end='')
	print()


(H, W) = map(int, input().split())
P = [input() for _ in range(H)]
red = [['.' for x in range(W)] for y in range(H)]
blue = [['.' for x in range(W)] for y in range(H)]
for i in range(H):
	red[i][0] = '#'
	blue[i][W - 1] = '#'
	for j in range(1, W - 1):
		if i % 2 == 0:
			red[i][j] = '#'
		else:
			blue[i][j] = '#'
for i in range(1, H - 1):
	for j in range(1, W - 1):
		if P[i][j] == '#':
			red[i][j] = '#'
			blue[i][j] = '#'
for i in range(H):
	print(''.join(red[i]))
print('')
for i in range(H):
	print(''.join(blue[i]))


(H, W) = map(int, input().split())
G = [list(map(lambda x: x == '#', input().strip())) for _ in range(H)]
Takahashi = [[False] * W for _ in range(H)]
Aoki = [[False] * W for _ in range(H)]
for h in range(H):
	for w in range(W):
		if w == 0:
			Takahashi[h][w] = True
		elif not h & 1:
			Aoki[h][w] = True
		if w == W - 1:
			Aoki[h][w] = True
		elif h & 1:
			Takahashi[h][w] = True
		if G[h][w]:
			Takahashi[h][w] = True
			Aoki[h][w] = True
print('\n'.join([''.join(['#' if s else '.' for s in Takahashi[i]]) for i in range(H)]))
print('')
print('\n'.join([''.join(['#' if s else '.' for s in Aoki[i]]) for i in range(H)]))


(H, W) = map(int, input().split())
A1 = ['#' * W]
A2 = ['.' * W]
input()
for i in range(H - 2):
	A = input()
	s = ''
	for (j, c) in enumerate(A):
		if j % 2 or c == '#':
			s += '#'
		else:
			s += '.'
	A1.append(s)
	s = ''
	for (j, c) in enumerate(A):
		if j % 2 == 0 or c == '#':
			s += '#'
		else:
			s += '.'
	A2.append(s)
A1.append('.' * W)
A2.append('#' * W)
print('\n'.join(A1))
print()
print('\n'.join(A2))


(H, W) = map(int, input().split())
A = []
for i in range(H):
	A.append(input())
red = [['.' for w in range(W)] for _ in range(H)]
blue = [['.' for w in range(W)] for _ in range(H)]
for i in range(H):
	if i % 2 == 0:
		red[i] = ['#' for w in range(W)]
		red[i][-1] = '.'
	else:
		red[i][0] = '#'
for i in range(H):
	if i % 2 == 0:
		blue[i][-1] = '#'
	else:
		blue[i] = ['#' for w in range(W)]
		blue[i][0] = '.'
for i in range(H):
	for j in range(W):
		if A[i][j] == '#':
			red[i][j] = '#'
			blue[i][j] = '#'
for i in range(H):
	print(''.join(red[i]))
print('')
for i in range(H):
	print(''.join(blue[i]))


(H, W) = map(int, input().split())
a = [list(input()) for _ in range(H)]
ans = [['r' for _ in range(W)]] + [['.' for _ in range(W)] for _ in range(H - 2)] + [['b' for _ in range(W)]]
for h in range(1, H - 1):
	for w in range(W):
		if a[h][w] == '#':
			ans[h][w] = 'p'
		elif w % 2 == 0:
			ans[h][w] = 'r'
		else:
			ans[h][w] = 'b'
r = [['.' for _ in range(W)] for _ in range(H)]
for h in range(H):
	for w in range(W):
		if ans[h][w] == 'p' or ans[h][w] == 'r':
			r[h][w] = '#'
for h in range(H):
	print(''.join(r[h]))
print('\n')
b = [['.' for _ in range(W)] for _ in range(H)]
for h in range(H):
	for w in range(W):
		if ans[h][w] == 'p' or ans[h][w] == 'b':
			b[h][w] = '#'
for h in range(H):
	print(''.join(b[h]))


(h, w) = map(int, input().split())
G = [input() for _ in range(h)]
R = [['.'] * w for _ in range(h)]
B = [['.'] * w for _ in range(h)]
for i in range(1, h - 1):
	if i % 2:
		R[i] = list('.' + '#' * (w - 2) + '.')
		B[i] = list(G[i])
	else:
		B[i] = list('.' + '#' * (w - 2) + '.')
		R[i] = list(G[i])
for i in range(h):
	R[i][0] = '#'
	B[i][-1] = '#'
for r in R:
	print(''.join(r))
print()
for b in B:
	print(''.join(b))


def examA():
	(A, B, C) = LI()
	ans = min(A * B * (C % 2), A * C * (B % 2), B * C * (A % 2))
	print(ans)
	return

def examB():

	class segment_:

		def __init__(self, A, n, segfunc):
			self.ide_ele = inf
			self.num = 1 << (n - 1).bit_length()
			self.seg = [self.ide_ele] * 2 * self.num
			self.segfunc = segfunc
			for i in range(n):
				self.seg[i + self.num] = A[i]
			for i in range(self.num - 1, 0, -1):
				self.seg[i] = self.segfunc(self.seg[2 * i], self.seg[2 * i + 1])

		def update(self, k, r):
			k += self.num
			self.seg[k] = r
			while k:
				k >>= 1
				self.seg[k] = self.segfunc(self.seg[k * 2], self.seg[k * 2 + 1])

		def update1(self, k):
			k += self.num
			self.seg[k] += 1
			while k:
				k >>= 1
				self.seg[k] = self.segfunc(self.seg[k * 2], self.seg[k * 2 + 1])

		def updateneg1(self, k):
			k += self.num
			self.seg[k] -= 1
			while k:
				k >>= 1
				self.seg[k] = self.segfunc(self.seg[k * 2], self.seg[k * 2 + 1])

		def query(self, p, q):
			if q < p:
				return self.ide_ele
			p += self.num
			q += self.num
			res = self.ide_ele
			while p < q:
				if p & 1 == 1:
					res = self.segfunc(res, self.seg[p])
					p += 1
				if q & 1 == 1:
					q -= 1
					res = self.segfunc(res, self.seg[q])
				p >>= 1
				q >>= 1
			return res
	(N, x) = LI()
	A = LI()
	Seg_min = segment_(A, N, lambda a, b: min(a, b))
	ans = inf
	for k in range(N):
		cur = 0
		for j in range(N):
			if j - k >= 0:
				now = Seg_min.query(j - k, j + 1)
			else:
				now = min(Seg_min.query(0, j + 1), Seg_min.query(N - (k - j), N))
			cur += now
		ans = min(ans, cur + k * x)
	print(ans)
	return

def examC():
	(H, W) = LI()
	A = [SI() for _ in range(H)]
	T = ['' for _ in range(H)]
	S = ['' for _ in range(H)]
	for h in range(H):
		T[h] += '#'
		S[h] += '.'
	for h in range(H):
		for w in range(1, W - 1):
			if h % 2 == 0:
				T[h] += '#'
			elif A[h][w] == '#':
				T[h] += '#'
			else:
				T[h] += '.'
			if h % 2 == 1:
				S[h] += '#'
			elif A[h][w] == '#':
				S[h] += '#'
			else:
				S[h] += '.'
	for h in range(H):
		T[h] += '.'
		S[h] += '#'
	for v in T:
		print(v)
	print()
	for v in S:
		print(v)
	return

def examD():
	(N, K) = LI()
	A = LI()
	V = [[] for _ in range(N)]
	ans = 0
	if A[0] != 1:
		ans += 1
		A[0] = 1
	for i in range(1, N):
		V[A[i] - 1].append(i)

	def dfs(p, s):
		depth = 0
		cnt = 0
		for i in V[s]:
			(d, c) = dfs(s, i)
			depth = max(depth, d)
			cnt += c
		depth += 1
		if depth == K and p != 0:
			depth = 0
			cnt += 1
		return (depth, cnt)
	(_, cnt) = dfs(0, 0)
	ans += cnt
	print(ans)
	return

def examE():
	ans = 0
	print(ans)
	return

def examF():
	ans = 0
	print(ans)
	return
import sys, copy, bisect, itertools, heapq, math
from heapq import heappop, heappush, heapify
from collections import Counter, defaultdict, deque

def I():
	return int(sys.stdin.readline())

def LI():
	return list(map(int, sys.stdin.readline().split()))

def LFI():
	return list(map(float, sys.stdin.readline().split()))

def LSI():
	return list(map(str, sys.stdin.readline().split()))

def LS():
	return sys.stdin.readline().split()

def SI():
	return sys.stdin.readline().strip()
global mod, mod2, inf, alphabet
mod = 10 ** 9 + 7
mod2 = 998244353
inf = 10 ** 18
alphabet = [chr(ord('a') + i) for i in range(26)]
sys.setrecursionlimit(10 ** 6)
examC()


(h, w) = map(int, input().split())
a = [list(input()) for _ in range(h)]
u = [['.'] * w for _ in range(h)]
v = [['.'] * w for _ in range(h)]
for i in range(h):
	for j in range(w):
		if a[i][j] == '#':
			(u[i][j], v[i][j]) = ('#', '#')
		elif i == 0:
			u[i][j] = '#'
		elif i == h - 1:
			v[i][j] = '#'
		elif j % 2 == 0:
			u[i][j] = '#'
		else:
			v[i][j] = '#'
for s in u:
	print(''.join(s))
print()
for t in v:
	print(''.join(t))


from collections import defaultdict, deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random

def LI():
	return [int(x) for x in sys.stdin.readline().split()]

def I():
	return int(sys.stdin.readline())

def LS():
	return [list(x) for x in sys.stdin.readline().split()]

def S():
	res = list(sys.stdin.readline())
	if res[-1] == '\n':
		return res[:-1]
	return res

def IR(n):
	return [I() for i in range(n)]

def LIR(n):
	return [LI() for i in range(n)]

def SR(n):
	return [S() for i in range(n)]

def LSR(n):
	return [LS() for i in range(n)]
sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
	(h, w) = LI()
	a = [input() for i in range(h)]
	r = [list('#' + '.' * (w - 1)) for i in range(h)]
	b = [list('.' * (w - 1) + '#') for i in range(h)]
	for i in range(h):
		if i & 1:
			r[i] = list('#' * (w - 1) + '.')
		else:
			b[i] = list('.' + '#' * (w - 1))
	for i in range(h):
		for j in range(w):
			if a[i][j] == '#':
				r[i][j] = '#'
				b[i][j] = '#'
	for i in r:
		print(*i, sep='')
	print()
	for i in b:
		print(*i, sep='')
	return
solve()


(h, w) = map(int, input().split())
r = [list('#' + '#.'[i % 2] * (w - 2) + '.') for i in range(h)]
b = [list('.' + '.#'[i % 2] * (w - 2) + '#') for i in range(h)]
for i in range(h):
	t = input()
	for j in range(w):
		if t[j] == '#':
			r[i][j] = b[i][j] = '#'
for t in r:
	print(''.join(t))
print()
for t in b:
	print(''.join(t))


(h, w) = map(int, input().split())
a = [['.'] * w for _ in range(h)]
b = [['.'] * w for _ in range(h)]
for i in range(h):
	s = input()
	for j in range(w):
		if i % 2 and j != w - 1 or j == 0 or s[j] == '#':
			a[i][j] = '#'
		if (i + 1) % 2 and j != 0 or j == w - 1 or s[j] == '#':
			b[i][j] = '#'
for x in a + [[]] + b:
	print(''.join(x))


(h, w) = (int(i) for i in input().split())
a = [input() for i in range(h)]
(r, b) = ([['#'] for i in range(h)], [['.'] for i in range(h)])
x = ['#', '.']
for i in range(h):
	for j in range(1, w - 1):
		if a[i][j] == '#':
			r[i].append('#')
			b[i].append('#')
		else:
			r[i].append(x[i % 2])
			b[i].append(x[1 - i % 2])
	r[i].append('.')
	b[i].append('#')
for i in range(h):
	print(''.join(r[i]))
print()
for i in range(h):
	print(''.join(b[i]))


(h, w) = map(int, input().split())
empty_row = ['.'] * w
a_empty_row = ['#'] + ['.'] * (w - 1)
a_filled_row = ['#'] * (w - 1) + ['.']
b_empty_row = ['.'] * (w - 1) + ['#']
b_filled_row = ['.'] + ['#'] * (w - 1)
violet = [input() for _ in range(h)]
aaa = []
bbb = []
for i in range(h):
	if i % 2 == 0:
		aaa.append(a_filled_row.copy())
		bbb.append(b_empty_row.copy())
	else:
		aaa.append(a_empty_row.copy())
		bbb.append(b_filled_row.copy())
for i in range(1, h - 1):
	for j in range(1, w - 1):
		if violet[i][j] == '#':
			aaa[i][j] = '#'
			bbb[i][j] = '#'
print('\n'.join((''.join(row) for row in aaa)))
print()
print('\n'.join((''.join(row) for row in bbb)))


(H, W) = map(int, input().split())
Map = [input() for i in range(H)]
(Base1, Base2) = ([], [])
for i in range(H):
	if i % 2 == 0:
		Base1.append(['#'] * (W - 1) + ['.'])
		Base2.append(['.'] * (W - 1) + ['#'])
	elif i % 2 == 1:
		Base1.append(['#'] + ['.'] * (W - 1))
		Base2.append(['.'] + ['#'] * (W - 1))
for i in range(H):
	for j in range(W):
		if Map[i][j] == '#':
			(Base1[i][j], Base2[i][j]) = ('#', '#')
for i in range(H):
	print(''.join(Base1[i]))
print()
for i in range(H):
	print(''.join(Base2[i]))


(h, w) = map(int, input().split())
a = [list(input()) for _ in range(h)]

def printboard(board):
	for i in board:
		print(*i, sep='')
red = [['.'] * w for _ in range(h)]
blue = [['.'] * w for _ in range(h)]
for i in range(h):
	red[i][0] = '#'
	blue[i][-1] = '#'
	for j in range(1, w - 1):
		if i % 2 == 0:
			red[i][j] = '#'
		else:
			blue[i][j] = '#'
for i in range(h):
	for j in range(w):
		if a[i][j] == '#':
			red[i][j] = '#'
			blue[i][j] = '#'
printboard(red)
print()
printboard(blue)


(H, W) = [int(i) for i in input().split()]
a = [input() for i in range(H)]
R = [[False for i in range(W)] for j in range(H)]
B = [[False for i in range(W)] for j in range(H)]
for i in range(H):
	R[i][0] = B[i][-1] = True
	if i % 2 == 0:
		for j in range(1, W - 1):
			R[i][j] = True
	else:
		for j in range(1, W - 1):
			B[i][j] = True
for i in range(H):
	for j in range(W):
		if a[i][j] == '#':
			R[i][j] = B[i][j] = True
for row in R:
	for col in row:
		print('#' if col else '.', end='')
	print()
print()
for row in B:
	for col in row:
		print('#' if col else '.', end='')
	print()


(H, W) = map(int, input().split())
src = [input() for i in range(H)]
ans1 = [['#'] + ['.'] * (W - 1) for i in range(H)]
ans2 = [['.'] * (W - 1) + ['#'] for i in range(H)]
for i in range(1, H - 1):
	for j in range(1, W - 1):
		if i % 2:
			ans1[i][j] = '#'
			ans2[i][j] = src[i][j]
		else:
			ans1[i][j] = src[i][j]
			ans2[i][j] = '#'
for row in ans1:
	print(''.join(row))
print('')
for row in ans2:
	print(''.join(row))