#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 > graph; vector< int > dist, match; vector< bool > used, vv; HopcroftKarp(int n, int m) : graph(n), match(m, -1), used(n) {} void add_edge(int u, int v) { graph[u].push_back(v); } void bfs() { dist.assign(graph.size(), -1); queue< int > que; for(int i = 0; i < graph.size(); i++) { if(!used[i]) { que.emplace(i); dist[i] = 0; } } while(!que.empty()) { int a = que.front(); que.pop(); for(auto &b : graph[a]) { int c = match[b]; if(c >= 0 && dist[c] == -1) { dist[c] = dist[a] + 1; que.emplace(c); } } } } bool dfs(int a) { vv[a] = true; for(auto &b : graph[a]) { int c = match[b]; if(c < 0 || (!vv[c] && dist[c] == dist[a] + 1 && dfs(c))) { match[b] = a; used[a] = true; return (true); } } return (false); } int bipartite_matching() { int ret = 0; while(true) { bfs(); vv.assign(graph.size(), false); int flow = 0; for(int i = 0; i < graph.size(); i++) { if(!used[i] && dfs(i)) ++flow; } if(flow == 0) return (ret); ret += flow; } } void output() { for(int i = 0; i < match.size(); i++) { if(~match[i]) { cout << match[i] << "-" << i << endl; } } } }; 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) 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; rep(i,0,n) { for (string &v : u[i]) { x.eb(v, i); } } sort(all(x)); vector> G(n); vector y; rep(i,0,len(x)) { if (i == 0 || x[i-1].fi != x[i].fi) { G[x[i].se].eb(len(y)); y.eb(x[i].fi); } else { G[x[i].se].eb(len(y)-1); } } // rep(i,0,len(y)) cout << y[i] << endl; HopcroftKarp hk(n, len(y)); rep(i,0,n) { for (int j : G[i]) { hk.add_edge(i, j); } } if (hk.bipartite_matching() < n) { cout << -1 << endl; } vector ans(n); rep(i,0,len(y)) { if (~hk.match[i]) { ans[hk.match[i]] = i; } } rep(i,0,n) cout << y[ans[i]] << endl; return 0; }