# input import sys input = sys.stdin.readline II = lambda : int(input()) MI = lambda : map(int, input().split()) LI = lambda : [int(a) for a in input().split()] SI = lambda : input().rstrip() LLI = lambda n : [[int(a) for a in input().split()] for _ in range(n)] LSI = lambda n : [input().rstrip() for _ in range(n)] MI_1 = lambda : map(lambda x:int(x)-1, input().split()) LI_1 = lambda : [int(a)-1 for a in input().split()] mod = 998244353 inf = 1001001001001001001 ordalp = lambda s : ord(s)-65 if s.isupper() else ord(s)-97 ordallalp = lambda s : ord(s)-39 if s.isupper() else ord(s)-97 yes = lambda : print("Yes") no = lambda : print("No") yn = lambda flag : print("Yes" if flag else "No") prinf = lambda ans : print(ans if ans < 1000001001001001001 else -1) alplow = "abcdefghijklmnopqrstuvwxyz" alpup = "ABCDEFGHIJKLMNOPQRSTUVWXYZ" alpall = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ" URDL = {'U':(-1,0), 'R':(0,1), 'D':(1,0), 'L':(0,-1)} DIR_4 = [[-1,0],[0,1],[1,0],[0,-1]] DIR_8 = [[-1,0],[-1,1],[0,1],[1,1],[1,0],[1,-1],[0,-1],[-1,-1]] DIR_BISHOP = [[-1,1],[1,1],[1,-1],[-1,-1]] prime60 = [2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59] sys.set_int_max_str_digits(0) # sys.setrecursionlimit(10**6) # import pypyjit # pypyjit.set_param('max_unroll_recursion=-1') from collections import defaultdict,deque from heapq import heappop,heappush from bisect import bisect_left,bisect_right DD = defaultdict BSL = bisect_left BSR = bisect_right import collections class mf_graph: n = 0 g = [] def __init__(self, n_): self.n = n_ self.g = [[] for i in range(self.n)] self.pos = [] class _edge: to = 0 rev = 0 cap = 0 def __init__(self, to_, rev_, cap_): self.to = to_ self.rev = rev_ self.cap = cap_ class edge: From = 0 To = 0 Cap = 0 Flow = 0 def __init__(self, from_, to_, cap_, flow_): self.From = from_ self.To = to_ self.Cap = cap_ self.Flow = flow_ def add_edge(self, From_, To_, Cap_): assert 0 <= From_ and From_ < self.n assert 0 <= To_ and To_ < self.n assert 0 <= Cap_ m = len(self.pos) self.pos.append((From_, len(self.g[From_]))) from_id = len(self.g[From_]) to_id = len(self.g[To_]) if From_ == To_: to_id += 1 self.g[From_].append(self._edge(To_, to_id, Cap_)) self.g[To_].append(self._edge(From_, from_id, 0)) return m def get_edge(self, i): m = len(self.pos) assert 0 <= i and i < m _e = self.g[self.pos[i][0]][self.pos[i][1]] _re = self.g[_e.to][_e.rev] return self.edge(self.pos[i][0], _e.to, _e.cap + _re.cap, _re.cap) def edges(self, isdict=True): m = len(self.pos) result = [] for i in range(m): if isdict: e = self.get_edge(i) result.append( {"from": e.From, "to": e.To, "cap": e.Cap, "flow": e.Flow} ) else: result.append(self.get_edge(i)) return result def change_edge(self, i, new_cap, new_flow): m = len(self.pos) assert 0 <= i and i < m assert 0 <= new_flow and new_flow <= new_cap _e = self.g[self.pos[i][0]][self.pos[i][1]] _re = self.g[_e.to][_e.rev] _e.cap = new_cap - new_flow _re.cap = new_flow assert id(_e) == id(self.g[self.pos[i][0]][self.pos[i][1]]) assert id(_re) == id(self.g[_e.to][_e.rev]) def flow(self, s, t, flow_limit=(1 << 63) - 1): assert 0 <= s and s < self.n assert 0 <= t and t < self.n assert s != t level = [0 for i in range(self.n)] Iter = [0 for i in range(self.n)] que = collections.deque([]) def bfs(): for i in range(self.n): level[i] = -1 level[s] = 0 que.clear() que.append(s) while que: v = que.popleft() for e in self.g[v]: if e.cap == 0 or level[e.to] >= 0: continue level[e.to] = level[v] + 1 if e.to == t: return que.append(e.to) def dfs(v, up): if v == s: return up res = 0 level_v = level[v] for i in range(Iter[v], len(self.g[v])): e = self.g[v][i] assert id(e) == id(self.g[v][i]) if level_v <= level[e.to] or self.g[e.to][e.rev].cap == 0: continue d = dfs(e.to, min(up - res, self.g[e.to][e.rev].cap)) if d <= 0: continue self.g[v][i].cap += d self.g[e.to][e.rev].cap -= d res += d if res == up: return res level[v] = self.n return res flow = 0 while flow < flow_limit: bfs() if level[t] == -1: break Iter = [0 for i in range(self.n)] f = dfs(t, flow_limit - flow) if not (f): break flow += f return flow def min_cut(self, s): visited = [False for i in range(self.n)] que = collections.deque([s]) while que: p = que.popleft() visited[p] = True for e in self.g[p]: if e.cap and not (visited[e.to]): visited[e.to] = True que.append(e.to) return visited """ 面白い 検討がつかない 200 個列挙して、重複がないようにすればいいというはなしですね """ # しんどい # どうかこう def calc(t): ok = [] l = [0] * (n + 1) r = [0] * (n + 1) for i in reversed(range(n)): if t[i] == "(": l[i] = max(0, l[i+1] - 1) r[i] = min(n//2, r[i+1] - 1) elif t[i] == ")": l[i] = l[i+1] + 1 r[i] = min(n//2, r[i+1] + 1) else: l[i] = max(0, l[i+1] - 1) r[i] = min(n//2, r[i+1] + 1) if l[i] > r[i]: print(-1) exit() if not (l[0] <= 0 <= r[0]): print(-1) exit() # print(l, r) p = [] def dfs(i, d): if len(ok) == n: return if i == n: if d == 0: ok.append("".join(p)) return if t[i] in "(." and l[i+1] <= d + 1 <= r[i+1]: p.append("(") dfs(i + 1, d + 1) p.pop() if len(ok) == n: return if t[i] in ")." and l[i+1] <= d - 1 <= r[i+1]: p.append(")") dfs(i + 1, d - 1) p.pop() if len(ok) == n: return dfs(0, 0) return ok n = II() # g = mf_graph(n + n * n + 2) from random import shuffle class Bipartite_Matching: __slots__ = ("__M", "__N", "__edges", "__size", "__matching") def __init__(self, M: int, N: int): """ 部集合の大きさが M, N である二部グラフを生成する. Args: M (int): 部集合 1 の大きさ N (int): 部集合 2 の大きさ """ self.__M = M self.__N = N self.__edges: list[list[int]] = [[] for _ in range(M)] @property def M(self) -> int: """ 部集合 1 の大きさを返す. Returns: int: 部集合 1 の大きさ """ return self.__M @property def N(self) -> int: """ 部集合 2 の大きさを返す. Returns: int: 部集合 2 の大きさ """ return self.__N def add_edge(self, a: int, b: int): """ 辺 Aa と辺 Bb を結ぶ無向辺を追加する. Args: a (int): 部集合 1 側の頂点番号 b (int): 部集合 2 側の頂点番号 """ assert 0 <= a < self.M assert 0 <= b < self.N self.__edges[a].append(b) def calculate(self, matching = False): """ 最大マッチングを計算する (結果は property メソッドで参照する). Args: matching (bool, optional): True にすると, 最大マッチングの一例も一緒に求める. Defaults to False. """ for a in range(self.M): shuffle(self.__edges[a]) edge = self.__edges pre = [-1] * self.M root = [-1] * self.M p = [-1] * self.M q = [-1] * self.N updated = True size = 0 while updated: updated = False S = [] index = 0 for i in range(self.M): if p[i] == -1: root[i] = i S.append(i) while index < len(S): v = S[index] index += 1 if p[root[v]] != -1: continue for u in edge[v]: if q[u] == -1: while u != -1: q[u] = v p[v], u = u, p[v] v = pre[v] updated = True size += 1 break u = q[u] if pre[u] != -1: continue pre[u] = v root[u] = root[v] S.append(u) if updated: pre = [-1] * self.M root = [-1] * self.M self.__size = size if not matching: self.__matching = None A = [-1] * self.M B = [-1] * self.N for i in range(self.M): if p[i] != -1: A[i] = p[i] B[p[i]] = i self.__matching = (A, B) @property def max_matching_size(self) -> int: """ calculate で求めた最大マッチングのサイズを求める. Returns: int: 最大マッチングのサイズ """ return self.__size @property def max_matching(self) -> tuple[list[int], list[int]]: """ calculate で求めた最大マッチングの一例を求める. Returns: tuple[list[int], list[int]]: (A, B) A[i] が -1 ではないとき, 辺 (i, A[i]) がマッチングとして採用されている. A[i] = -1 のときはマッチングの頂点として採用されていない. B[j] が -1 ではないとき, 辺 (B[j], j) がマッチングとして採用されている. B[j] = -1 のときはマッチングの頂点として採用されていない. """ return self.__matching # s_ = n + (n * n) # t_ = s_ + 1 idx = 0 idxs = dict() sss = [] g = Bipartite_Matching(n, n * n) e = [] for i in range(n): t = SI() ss = calc(t) for s in ss: if s in idxs: g.add_edge(i, idxs[s]) else: g.add_edge(i, idx) idxs[s] = idx idx += 1 sss.append(s) g.calculate(True) if g.max_matching_size != n: print(-1) exit() a, b = g.max_matching # print(a, b) ans = [None] * n for i in range(n): ans[i] = sss[a[i]] for s in ans: print(s)