from sys import stdin input = stdin.readline from collections import deque, defaultdict import sys sys.setrecursionlimit(10**6) class HopcroftKarp: def __init__(self, N1, N2): self.N1 = N1 self.N2 = N2 self.G = [[] for _ in range(self.N1+1)] self.pair1 = [0]*(self.N1+1) self.pair2 = [0]*(self.N2+1) self.matching_size = -1 def add_edge(self, fr, to): self.G[fr].append(to) def bfs(self): que = deque() for i in range(1, self.N1+1): if self.pair1[i] == 0: self.dist[i] = 0 que.append(i) else: self.dist[i] = INF self.dist[0] = INF while que: n = que.popleft() if self.dist[n] < self.dist[0]: for v in self.G[n]: if self.dist[self.pair2[v]] == INF: self.dist[self.pair2[v]] = self.dist[n]+1 que.append(self.pair2[v]) return self.dist[0] != INF def dfs(self, n): if n != 0: for v in self.G[n]: if self.dist[self.pair2[v]] == self.dist[n]+1: if self.dfs(self.pair2[v]): self.pair2[v] = n self.pair1[n] = v return True self.dist[n] = INF return False return True def flow(self): if self.matching_size != -1: return self.matching_size self.dist = [0]*(self.N1+1) ans = 0 while self.bfs(): for i in range(1, self.N1+1): if self.pair1[i] == 0 and self.dfs(i): ans += 1 self.matching_size = ans return ans def get_matching(self): if self.matching_size == -1: self.flow() ans = [] for i in range(1, self.N1+1): if self.pair1[i] != 0: ans.append((i, self.pair1[i])) return ans def minimum_vertex_cover(self): if self.matching_size == -1: self.flow() return self.matching_size def maximum_independent_set(self): return self.N1+self.N2-self.minimum_vertex_cover() def minimum_edge_cover(self): F = [False]*(self.N1+self.N2+1) for n in range(1, self.N1+1): F[n] = True for v in self.G[n]: F[self.N1+v] = True if sum(F) < self.N1+self.N2: return -1 if self.matching_size == -1: self.flow() return self.N1+self.N2-self.matching_size def preparation(self): if self.matching_size == -1: self.flow() L = self.N1+self.N2 G = [[] for _ in range(L+1)] for n in range(1, self.N1+1): for v in self.G[n]: if self.pair1[n] == v: G[self.N1+v].append(n) else: G[n].append(self.N1+v) visited = [False]*(L+1) que = deque() for i in range(1, self.N1+1): if self.pair1[i] == 0: visited[i] = True que.append(i) while que: n = que.popleft() for v in G[n]: if not visited[v]: visited[v] = True que.append(v) return visited def get_minimum_vertex_cover(self): visited = self.preparation() ans1 = [] ans2 = [] for i in range(1, self.N1+self.N2+1): if i <= self.N1 and not visited[i]: ans1.append(i) elif self.N1+1 <= i and visited[i]: ans2.append(i-self.N1) return ans1, ans2 def get_maximum_independent_set(self): visited = self.preparation() ans1 = [] ans2 = [] for i in range(1, self.N1+self.N2+1): if i <= self.N1 and visited[i]: ans1.append(i) elif self.N1+1 <= i and not visited[i]: ans2.append(i-self.N1) return ans1, ans2 def get_minimum_edge_cover(self): cnt = self.minimum_edge_cover() if cnt == -1: return None ans = [] pair = [-1]*(self.N1+self.N2+1) for n in range(1, self.N1+1): pair[n] = self.G[n][0] for v in self.G[n]: if pair[self.N1+v] == -1: pair[self.N1+v] = n for i in range(1, self.N1+self.N2+1): if i <= self.N1 and self.pair1[i] != 0: ans.append((i, self.pair1[i])) elif i <= self.N1 and self.pair1[i] == 0: ans.append((i, pair[i])) elif self.N1+1 <= i and self.pair2[i-self.N1] == 0: ans.append((pair[i], i-self.N1)) return ans HMOD = 1145141919810011 INF = 1<<60 N = int(input()) S = [input().rstrip("\n") for _ in range(N)] def dfs(idx1, idx2, dist): if idx2 == -1: C[idx1].append("".join(A[::-1])) return if dp[idx2][dist+1] != 0 and S[idx1][idx2] in [")", "."]: A.append(")") dfs(idx1, idx2-1, dist+1) A.pop() if N <= len(C[idx1]): return if 1 <= dist and dp[idx2][dist-1] != 0 and S[idx1][idx2] in ["(", "."]: A.append("(") dfs(idx1, idx2-1, dist-1) A.pop() if N <= len(C[idx1]): return C = [[] for _ in range(N)] for i in range(N): dp = [[0]*(N+1) for _ in range(N+1)] dp[0][0] = 1 for j, s in enumerate(S[i]): for k in range(N+1): if dp[j][k] == 0: continue if s == "(" or s == ".": dp[j+1][k+1] += dp[j][k] dp[j+1][k+1] %= HMOD if (s == ")" or s == ".") and 1 <= k: dp[j+1][k-1] += dp[j][k] dp[j+1][k-1] %= HMOD if dp[-1][0] == 0: exit(print(-1)) A = [] dfs(i, N-1, 0) idx1, idx2 = 0, 0 IDX = [-1]*N IDXR = [] D = defaultdict(int) DR = [] for i in range(N): if N <= len(C[i]): continue IDX[i] = idx1 IDXR.append(i) idx1 += 1 for c in C[i]: if c not in D: D[c] = idx2 DR.append(c) idx2 += 1 H = HopcroftKarp(idx1, idx2) for i in range(N): if N <= len(C[i]): continue for c in C[i]: H.add_edge(IDX[i]+1, D[c]+1) mat = H.get_matching() if len(mat) < idx1: exit(print(-1)) SET = set() for l, r in mat: S[IDXR[l-1]] = DR[r-1] h = 0 for a in DR[r-1]: h *= 2 h %= HMOD if a == "(": h += 1 else: h += 2 h %= HMOD SET.add(h) for i in range(N): if len(C[i]) < N: continue for c in C[i]: h = 0 for a in c: h *= 2 h %= HMOD if a == "(": h += 1 else: h += 2 h %= HMOD if h not in SET: SET.add(h) S[i] = c break for s in S: print(s)