#!/usr/bin/env python3 import sys sys.setrecursionlimit(10000) def main(): data = sys.stdin.read().strip().splitlines() N = int(data[0].strip()) rows = [data[i + 1].rstrip("\n") for i in range(N)] W = 2 * N - 1 # Locate pyramid span and prefix mine counts on that span L = [0] * N R = [0] * N width = [0] * N pref = [] # pref[r][a] = #mines in first a cells of row r (a in [0..width[r]]) total = 0 for r in range(N): s = rows[r] l = 0 while l < W and s[l] == '#': l += 1 rr = W - 1 while rr >= 0 and s[rr] == '#': rr -= 1 if l > rr: print("Impossible") return L[r], R[r] = l, rr w = rr - l + 1 width[r] = w p = [0] * (w + 1) for i, ch in enumerate(s[l:rr + 1], start=1): p[i] = p[i - 1] + (1 if ch == 'C' else 0) pref.append(p) total += p[w] if total % 2 == 1: print("Impossible") return target = total // 2 INF = 10**15 # Precompute range mins/maxes for the three "range" transitions # 1) ZPRE -> PART: a in [1 .. width[r-1]] # 2) PART -> PART: a in [2 .. width[r-1]] # 3) FPRE -> PART: a in [2 .. width[r] - 1] minStartZ = [INF] * N maxStartZ = [-INF] * N minStay = [INF] * N maxStay = [-INF] * N minStartF = [INF] * N maxStartF = [-INF] * N for r in range(N): w = width[r] if r >= 1 and width[r - 1] >= 1: mn = INF; mx = -INF for a in range(1, width[r - 1] + 1): v = pref[r][a] if v < mn: mn = v if v > mx: mx = v minStartZ[r] = mn; maxStartZ[r] = mx if width[r - 1] >= 2: mn = INF; mx = -INF for a in range(2, width[r - 1] + 1): v = pref[r][a] if v < mn: mn = v if v > mx: mx = v minStay[r] = mn; maxStay[r] = mx if w >= 3: mn = INF; mx = -INF for a in range(2, w): v = pref[r][a] if v < mn: mn = v if v > mx: mx = v minStartF[r] = mn; maxStartF[r] = mx # Phases: 0=ZPRE, 1=FPRE, 2=PART, 3=ZAFT, 4=FAFT ZPRE, FPRE, PART, ZAFT, FAFT = 0, 1, 2, 3, 4 # Suffix min/max DP: min_suf[r][phase] = min mines A can still get from rows r..N-1 min_suf = [[INF] * 5 for _ in range(N + 1)] max_suf = [[-INF] * 5 for _ in range(N + 1)] for p in range(5): min_suf[N][p] = 0 max_suf[N][p] = 0 for r in range(N - 1, -1, -1): w = width[r] # ZAFT: only a=0 min_suf[r][ZAFT] = pref[r][0] + min_suf[r + 1][ZAFT] max_suf[r][ZAFT] = pref[r][0] + max_suf[r + 1][ZAFT] # FAFT: only a=w min_suf[r][FAFT] = pref[r][w] + min_suf[r + 1][FAFT] max_suf[r][FAFT] = pref[r][w] + max_suf[r + 1][FAFT] # PART: a=0 -> ZAFT, a=w -> FAFT, or keep PART with a in [2..width[r-1]] cmin = [pref[r][0] + min_suf[r + 1][ZAFT], pref[r][w] + min_suf[r + 1][FAFT]] cmax = [pref[r][0] + max_suf[r + 1][ZAFT], pref[r][w] + max_suf[r + 1][FAFT]] if r >= 1 and minStay[r] < INF: cmin.append(minStay[r] + min_suf[r + 1][PART]) cmax.append(maxStay[r] + max_suf[r + 1][PART]) min_suf[r][PART] = min(cmin) max_suf[r][PART] = max(cmax) # ZPRE: a=0 -> ZPRE, a=w -> FPRE, start PART with a in [1..width[r-1]] cmin = [pref[r][0] + min_suf[r + 1][ZPRE], pref[r][w] + min_suf[r + 1][FPRE]] cmax = [pref[r][0] + max_suf[r + 1][ZPRE], pref[r][w] + max_suf[r + 1][FPRE]] if r >= 1 and minStartZ[r] < INF: cmin.append(minStartZ[r] + min_suf[r + 1][PART]) cmax.append(maxStartZ[r] + max_suf[r + 1][PART]) min_suf[r][ZPRE] = min(cmin) max_suf[r][ZPRE] = max(cmax) # FPRE: a=w -> FPRE, a=0 -> ZAFT, start PART with a in [2..w-1] cmin = [pref[r][w] + min_suf[r + 1][FPRE], pref[r][0] + min_suf[r + 1][ZAFT]] cmax = [pref[r][w] + max_suf[r + 1][FPRE], pref[r][0] + max_suf[r + 1][ZAFT]] if minStartF[r] < INF: cmin.append(minStartF[r] + min_suf[r + 1][PART]) cmax.append(maxStartF[r] + max_suf[r + 1][PART]) min_suf[r][FPRE] = min(cmin) max_suf[r][FPRE] = max(cmax) if not (min_suf[0][ZPRE] <= target <= max_suf[0][ZPRE]): print("Impossible") return # Reconstruct with a DFS guided by bounds (few candidates per row) from functools import lru_cache def pick_candidates(r, lo, hi, desired): # pref[r][a] is nondecreasing in a lo, hi = int(lo), int(hi) if lo > hi: return [] Lb, Rb = lo, hi best = None while Lb <= Rb: m = (Lb + Rb) // 2 if pref[r][m] >= desired: best = m Rb = m - 1 else: Lb = m + 1 cands = [] if best is not None: cands.append(best) if best - 1 >= lo: cands.append(best - 1) if best + 1 <= hi: cands.append(best + 1) else: cands.append(hi) if hi - 1 >= lo: cands.append(hi - 1) cands = sorted(set(cands), key=lambda a: (abs(pref[r][a] - desired), a)) return cands[:4] a_choice = [0] * N @lru_cache(maxsize=None) def dfs(r, phase, acc): if r == N: return acc == target w = width[r] # Propose options in a good order opts = [] if phase == ZPRE: # try making this row full first (helps tough N=2 cases), then zero, then start PART opts.append((w, 1)) # FPRE opts.append((0, 0)) # stay ZPRE if r >= 1 and width[r - 1] >= 1: desired = target - acc - (min_suf[r + 1][2] + max_suf[r + 1][2]) / 2 for a in pick_candidates(r, 1, width[r - 1], desired): opts.append((a, 2)) # PART elif phase == FPRE: if w >= 3: desired = target - acc - (min_suf[r + 1][2] + max_suf[r + 1][2]) / 2 for a in pick_candidates(r, 2, w - 1, desired): opts.append((a, 2)) # PART opts.append((0, 3)) # ZAFT opts.append((w, 1)) # stay FPRE elif phase == PART: if r >= 1 and width[r - 1] >= 2: desired = target - acc - (min_suf[r + 1][2] + max_suf[r + 1][2]) / 2 for a in pick_candidates(r, 2, width[r - 1], desired): opts.append((a, 2)) # stay PART opts.append((0, 3)) # ZAFT opts.append((w, 4)) # FAFT elif phase == ZAFT: opts = [(0, 3)] else: # FAFT opts = [(w, 4)] # prune by feasibility window feasible = [] for a, np in opts: add = pref[r][a] lo = add + min_suf[r + 1][np] hi = add + max_suf[r + 1][np] if acc + lo <= target <= acc + hi: feasible.append((a, np)) # Try extremes too if nothing survived if not feasible: extra = [] if phase == ZPRE and r >= 1 and width[r - 1] >= 1: extra += [(1, 2), (width[r - 1], 2)] if phase == FPRE and w >= 3: extra += [(2, 2), (w - 1, 2)] if phase == PART and r >= 1 and width[r - 1] >= 2: extra += [(2, 2), (width[r - 1], 2)] for a, np in extra: add = pref[r][a] if acc + add + min_suf[r + 1][np] <= target <= acc + add + max_suf[r + 1][np]: feasible.append((a, np)) for a, np in feasible: a_choice[r] = a if dfs(r + 1, np, acc + pref[r][a]): return True return False if not dfs(0, ZPRE, 0): print("Impossible") return # Build and print labeling out = [] for r in range(N): w = width[r] a = a_choice[r] line = list(rows[r]) for k in range(w): c = L[r] + k line[c] = 'A' if k < a else 'B' out.append(''.join(line)) print('\n'.join(out)) if __name__ == "__main__": main()