# Try to partition the pyramid in many different orders, but choose exactly the wrong ones. N = int(input()) grid = [input().strip() for _ in range(N)] R, C = N, 2 * N - 1 copper = sum(line.count("C") for line in grid) def center_out_indices(n): mid = n // 2 yield mid for offset in range(1, n): left, right = mid - offset, mid + offset if left >= 0: yield left if right < n: yield right orders = { 'row-major': [(r, c) for r in range(R) for c in range(C)], 'row-major-flipped': [(r, c) for r in reversed(range(R)) for c in range(C)], 'column-major': [(r, c) for c in range(C) for r in range(R)], 'column-major-flipped': [(r, c) for c in range(C) for r in reversed(range(R))], 'diagonal': [ (r, c) for s in range(R + C - 1) # s = r + c for r in range(max(0, s - (C - 1)), min(R - 1, s) + 1) for c in [s - r] ], "diagonal-flipped": [ (r, c) for s in range(R + C - 1) for r in reversed(range(max(0, s - (C - 1)), min(R - 1, s) + 1)) for c in [s - r] ], # "column-center-out": [ # (r, c) # for c in center_out_indices(C) # for r in range(R) # ], "column-center-out-flipped": [ (r, c) for c in center_out_indices(C) for r in reversed(range(R)) ], #"row-major-column-center-out": [ # (r, c) # for r in range(R) # for c in center_out_indices(C) # ], "row-major-flipped-column-center-out": [ (r, c) for r in reversed(range(R)) for c in center_out_indices(C) ] } def num_components(packing, tribe): parent, rank = {}, {} def find(t): if t not in parent: parent[t] = t rank[t] = 0 root = t while parent[root] != root: root = parent[root] # Path compression while t != root: parent[t], t = root, parent[t] return root def union(s, t): ps, pt = find(s), find(t) if ps == pt: return if rank[ps] < rank[pt]: parent[ps] = pt elif rank[ps] > rank[pt]: parent[pt] = ps else: parent[pt] = ps rank[ps] += 1 for r in range(R): for c in range(C): if packing[r][c] == tribe: parent[(r, c)] = (r, c) rank[(r, c)] = 0 for r in range(R): for c in range(C): if packing[r][c] != tribe: continue if r < R - 1 and packing[r + 1][c] == tribe: union((r, c), (r + 1, c)) if c < C - 1 and packing[r][c + 1] == tribe: union((r, c), (r, c + 1)) return len( {find(cell) for cell in parent}) def try_order(order): solution = [["?"] * C for _ in range(R)] tribe = "A" total = {"A": 0, "B": 0} for r, c in order: if grid[r][c] == "#": solution[r][c] = "#" else: solution[r][c] = tribe if grid[r][c] == "C": total[tribe] += 1 if total["A"] >= copper // 2: tribe = "B" return solution if num_components(solution, 'A') == num_components(solution, 'B') == 1 and total["A"] == total["B"] else None for t, o in orders.items(): solution = try_order(o) if solution is not None: for line in solution: print("".join(line)) break else: print("Impossible")