// # pragma GCC target("avx2") // # pragma GCC optimize("O3") // # pragma GCC optimize("unroll-loops") #ifdef harurun #define debug(x) cerr<<#x<<": "< using namespace std; #if __has_include() #include using namespace atcoder; using mint = modint998244353; // using mint = modint1000000007; // using mint = double; #endif //define using ll = long long; using ull = unsigned long long; using pii = pair; using pll = pair; using vi = vector; using vll = vector; #define rep(i,l,r) for (int i = (int)(l); i < (int)(r); i++) #define rrep(i,l,r) for (int i = (int)(r-1); i >= (int)(l); i--) #define len(x) (int)(x).size() #define all(x) (x).begin(), (x).end() #define elif else if #define pb push_back #define eb emplace_back #define fi first #define se second const int inf = 1e9; const long long infl = 1LL<<60; const int mod = 998244353; ll pow(ll a, ll b, ll p){ ll ans = 1; while(b){ if(b & 1) (ans *= a) %= p; (a *= a) %= p; b /= 2; } return ans; } template bool chmin(T& a, const U& b){ if(a > T(b)){ a = b; return 1; } return 0; } template bool chmax(T& a, const U& b){ if(a < T(b)){ a = b; return 1; } return 0; } template using spq = priority_queue, greater>; templateistream& operator>>(istream& i, vector& v) {for(int j = 0; j < (int)(v).size(); j++) i >> v[j]; return i;} struct IoSetup { IoSetup() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); cerr << fixed << setprecision(15); } } iosetup; using ll = long long; #define rep(i, n) for (ll i = 0; i < ll(n); i++) #define rep2(i, l, r) for (ll i = ll(l); i < ll(r); i++) using vi = vector; using vvi = vector; using vll = vector; mt19937 engine; vector> Bipartite_Mathing(int n, int m, vector> &edges) { shuffle(edges.begin(),edges.end(),engine); vi G(edges.size()), L(n, -1), R(m, -1), deg(n + 1), a, p, q(n); for (auto &[x, y] : edges) deg[x]++; rep(i, n) deg[i + 1] += deg[i]; for (auto &[x, y] : edges) G[--deg[x]] = y; while (true) { a.assign(n, -1), p.assign(n, -1); int t = 0; rep(i, n) { if (L[i] == -1) { q[t++] = a[i] = p[i] = i; } } bool match = false; rep(i, t) { int x = q[i]; if (L[a[x]] != -1) continue; rep2(j, deg[x], deg[x + 1]) { int y = G[j]; if (R[y] == -1) { while (y != -1) { R[y] = x; swap(L[x], y); x = p[x]; } match = true; break; } if (p[R[y]] == -1) { q[t++] = y = R[y]; p[y] = x; a[y] = a[x]; } } } if (!match) break; } vector> res; rep(i, L.size()) { if (L[i] != -1) res.push_back({i, L[i]}); } return res; } vector calc(string t) { int n = len(t); vector ok; vi l(n + 1, 0), r(n + 1, 0); rrep(i, 0, 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] = max(0, 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] || r[i] < 0){ cout << -1 << endl; exit(0); } } if (not (l[0] <= 0 and 0 <= r[0])) { cout << -1 << endl; exit(0); } string p(n, ' '); auto dfs = [&](auto& dfs, int i, int d) -> void { if (len(ok) == n) return; if (i == n) { if (d == 0) ok.push_back(p); return; } if ((t[i] == '(' || t[i] == '.') and l[i+1] <= d + 1 and d + 1 <= r[i+1]) { p[i] = '('; dfs(dfs, i + 1, d + 1); } if (len(ok) == n) return; if ((t[i] == ')' || t[i] == '.') and l[i+1] <= d - 1 and d - 1 <= r[i+1]) { p[i] = ')'; dfs(dfs, i + 1, d - 1); } if (len(ok) == n) return; }; dfs(dfs, 0, 0); return ok; } int main(){ int n; cin >> n; unordered_map idxs; int idx = 0; vector sss; vector e; rep2(i, 0, n){ string t; cin >> t; auto ss = calc(t); for (auto s : ss){ if (not idxs.count(s)){ idxs[s] = idx; idx++; sss.pb(s); } e.push_back({i, idxs[s]}); } } vector> ans = Bipartite_Mathing(n, idx, e); if (len(ans) != n){ cout << -1 << endl; }else{ vector tmp(n); for (auto [a, b] : ans){ tmp[a] = sss[b]; } rep2(i, 0, n){ cout << tmp[i] << endl; } } }