#include #define fi first #define se second #define rep(i,s,n) for (int i = (s); i < (n); ++i) #define rrep(i,g,n) for (int i = (n)-1; i >= (g); --i) #define all(a) a.begin(),a.end() #define rall(a) a.rbegin(),a.rend() #define len(x) (int)(x).size() #define dup(x,y) (((x)+(y)-1)/(y)) #define pb push_back #define eb emplace_back #define Field(T) vector> using namespace std; using ll = long long; using ull = unsigned long long; template using pq = priority_queue,greater>; using P = pair; templatebool chmax(T&a,T b){if(abool chmin(T&a,T b){if(b struct MaxFlow { struct edge { int to; T cap; int rev; bool is_rev; }; vector> G; vector dist, iter; MaxFlow() = default; explicit MaxFlow(int n) : G(n) {} void add_edge(int from, int to, T cap = 1) { G[from].emplace_back(edge{to, cap, (int)G[to].size(), 0}); G[to].emplace_back(edge{from, 0, (int)G[from].size()-1, 1}); } void debug() { for (int i = 0; i < (int)G.size(); ++i) { for (edge &e : G[i]) { if (e.is_rev) continue; edge &rev_e = G[e.to][e.rev]; cout << i << " -> " << e.to << " : " << "(" << rev_e.cap << "/" << e.cap + rev_e.cap << ")" << endl; } } } void bfs(const int &s) { dist.assign(G.size(), -1); dist[s] = 0; queue que; que.push(s); while(!que.empty()) { int v = que.front(); que.pop(); for (edge &e : G[v]) { if (e.cap == 0 || dist[e.to] >= 0) continue; dist[e.to] = dist[v] + 1; que.push(e.to); } } } T dfs(int v, const int &t, T f) { if (v == t) return f; T ret = 0; for (int& i = iter[v]; i < (int)G[v].size(); ++i) { edge& e = G[v][i]; if (e.cap == 0 || dist[v] >= dist[e.to]) continue; T d = dfs(e.to, t, min(f - ret, e.cap)); if (d == 0) continue; e.cap -= d; G[e.to][e.rev].cap += d; ret += d; if (f == ret) break; } return ret; } T flow(int s, int t, T f_limit = numeric_limits::max()) { T ret = 0; queue que; while(true) { bfs(s); if (dist[t] == -1) break; iter.assign(G.size(), 0); while(ret < f_limit) { T f = dfs(s, t, f_limit - ret); if (f == 0) break; ret += f; } } return ret; } vector min_cut(int s) { vector used(G.size(), 0); used[s] = 1; queue que; que.push(s); while(!que.empty()) { int v = que.front(); que.pop(); for (edge &e : G[v]) { if (e.cap > 0 && !used[e.to]) { used[e.to] = 1; que.push(e.to); } } } return used; } }; int main() { int n; cin >> n; vector t(n); rep(i,0,n) cin >> t[i]; function&, string&, string&, int, int, int)> f = [&](vector &v, string &s, string &t, int idx, int val, int cnt) { if (len(v) > n+1) return; if (idx == n) { v.eb(s); return; } if (t[idx] == '(' || t[idx] == '.') { if (cnt < n/2) { s[idx] = '('; f(v, s, t, idx+1, val+1, cnt+1); s[idx] = '.'; } } if (t[idx] == ')' || t[idx] == '.') { if (idx-cnt < n/2 && val > 0) { s[idx] = ')'; f(v, s, t, idx+1, val-1, cnt); s[idx] = '.'; } } }; vector> u(n); string s(n, '.'); rep(i,0,n) f(u[i], s, t[i], 0, 0, 0); // rep(i,0,n) { // for (string v : u[i]) cout << v << endl; // cout << endl; // } vector x; map mp; rep(i,0,n) { for (string &v : u[i]) { x.eb(v); } } sort(all(x)); x.erase(unique(all(x)), x.end()); rep(i,0,len(x)) mp[x[i]] = i; // for (auto [v, cnt] : mp) { // cout << v << " " << cnt << endl; // } MaxFlow mf(n+len(mp)+2); rep(i,0,n) { mf.add_edge(n+len(mp), i); for (string &v : u[i]) { mf.add_edge(i, n+mp[v], 1); } } rep(j,0,len(mp)) mf.add_edge(n+j, n+len(mp)+1); if (mf.flow(n+len(mp), n+len(mp)+1) < n) { cout << -1 << endl; return 0; } rep(i,0,n) { for (auto &e : mf.G[i]) { if (e.is_rev) continue; if (e.cap == 0) { cout << x[e.to-n] << endl; } } } return 0; }