from collections import deque class Dinic: def __init__(self, n): self.n = n self.links = [[] for _ in range(n)] self.depth = None self.progress = None def add_link(self, _from, to, cap): self.links[_from].append([cap, to, len(self.links[to])]) self.links[to].append([0, _from, len(self.links[_from]) - 1]) def bfs(self, s): depth = [-1] * self.n depth[s] = 0 q = deque([s]) while q: v = q.popleft() for cap, to, rev in self.links[v]: if cap > 0 and depth[to] < 0: depth[to] = depth[v] + 1 q.append(to) self.depth = depth def dfs(self, v, t, flow): if v == t: return flow links_v = self.links[v] for i in range(self.progress[v], len(links_v)): self.progress[v] = i cap, to, rev = link = links_v[i] if cap == 0 or self.depth[v] >= self.depth[to]: continue d = self.dfs(to, t, min(flow, cap)) if d == 0: continue link[0] -= d self.links[to][rev][0] += d return d return 0 def max_flow(self, s, t): flow = 0 while True: self.bfs(s) if self.depth[t] < 0: return flow self.progress = [0] * self.n current_flow = self.dfs(s, t, float('inf')) while current_flow > 0: flow += current_flow current_flow = self.dfs(s, t, float('inf')) import pypyjit pypyjit.set_param('max_unroll_recursion=-1') N=int(input()) A=[] T={} G=[[] for i in range(N)] w=1 for e in range(N): s=input() dp=[[0]*(N+1) for i in range(N+1)] dp[N][0]=1 for i in range(N-1,-1,-1): for j in range(N+1): if dp[i+1][j]==0: continue if s[i]!='(': dp[i][j+1]=1 if s[i]!=')': if j>0: dp[i][j-1]=1 count=0 v=[0]*N def f(v,pos,now): global count global w if count>=N: return if pos==N: h=[0]*N for i in range(N): if v[i]==1: h[i]='(' else: h[i]=')' p=''.join(h) if not p in T: A.append(p) T[p]=w w+=1 c=T[p] G[e].append(c) count+=1 return if s[pos]!=')' and dp[pos+1][now+1]==1: v[pos]=1 f(v,pos+1,now+1) v[pos]=0 if s[pos]!='(' and now>0 and dp[pos+1][now-1]==1: v[pos]=-1 f(v,pos+1,now-1) v[pos]=0 f(v,0,0) Z=Dinic(N+w+2) for i in range(1,N+1): Z.add_link(0,i,1) for i in range(1,N+1): for pos in G[i-1]: Z.add_link(i,N+pos,1) for i in range(1,w+1): Z.add_link(N+i,N+w+1,1) ans=Z.max_flow(0,N+w+1) if ansN and cap==0: pos=e-N-1 print(A[pos])