# 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] = r[i+1] - 1 elif t[i] == ")": l[i] = l[i+1] + 1 r[i] = r[i+1] + 1 else: l[i] = max(0, l[i+1] - 1) r[i] = r[i+1] + 1 if l[i] > r[i]: print(-1) exit() if 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) s_ = n + (n * n) t_ = s_ + 1 idx = n idxs = dict() sss = [] for i in range(n): g.add_edge(s_, i, 1) t = SI() ss = calc(t) for s in ss: if s in idxs: g.add_edge(i, idxs[s], 1) else: g.add_edge(i, idx, 1) idxs[s] = idx idx += 1 sss.append(s) for i in range(n, idx): g.add_edge(i, t_, 1) f = g.flow(s_, t_) if f != n: print(-1) exit() ans = [None] *n for e in g.edges(): if e["flow"] == 1 and 0 <= e["from"] < n: ans[e["from"]] = sss[e["to"] - n] for s in ans: print(s)