#ifdef NACHIA #define _GLIBCXX_DEBUG #else // disable assert #define NDEBUG #endif #include #include #include #include using namespace std; using ll = long long; const ll INF = 1ll << 60; #define REP(i,n) for(ll i=0; i using V = vector; template void chmax(A& l, const B& r){ if(l < r) l = r; } template void chmin(A& l, const B& r){ if(r < l) l = r; } V concrete(string T, ll mx){ ll N = T.size() / 2; V> dp(N+2, V(N+2)); dp[0][0] = 1; REP(i,N+1) REP(j,N+1) if(i+j < N*2) if(dp[i][j]){ if(i > j){ dp[i][j] = 0; continue; } if(T[i+j] != ')') dp[i][j+1] = 1; if(T[i+j] != '(') dp[i+1][j] = 1; } V ans; string buf = T; auto dfs = [&](auto& dfs, ll i, ll j) -> void { if(ans.size() == mx) return; if(dp[i][j] == 0) return; if(i + j == 0){ ans.push_back(buf); return; } if(j && T[i+j-1] != ')'){ buf[i+j-1] = '('; dfs(dfs, i, j-1); } if(i && T[i+j-1] != '('){ buf[i+j-1] = ')'; dfs(dfs, i-1, j); } }; dfs(dfs, N, N); return ans; } #include namespace nachia{ template class CsrArray{ public: struct ListRange{ using iterator = typename std::vector::iterator; iterator begi, endi; iterator begin() const { return begi; } iterator end() const { return endi; } int size() const { return (int)std::distance(begi, endi); } Elem& operator[](int i) const { return begi[i]; } }; struct ConstListRange{ using iterator = typename std::vector::const_iterator; iterator begi, endi; iterator begin() const { return begi; } iterator end() const { return endi; } int size() const { return (int)std::distance(begi, endi); } const Elem& operator[](int i) const { return begi[i]; } }; private: int m_n; std::vector m_list; std::vector m_pos; public: CsrArray() : m_n(0), m_list(), m_pos() {} static CsrArray Construct(int n, std::vector> items){ CsrArray res; res.m_n = n; std::vector buf(n+1, 0); for(auto& [u,v] : items){ ++buf[u]; } for(int i=1; i<=n; i++) buf[i] += buf[i-1]; res.m_list.resize(buf[n]); for(int i=(int)items.size()-1; i>=0; i--){ res.m_list[--buf[items[i].first]] = std::move(items[i].second); } res.m_pos = std::move(buf); return res; } static CsrArray FromRaw(std::vector list, std::vector pos){ CsrArray res; res.m_n = pos.size() - 1; res.m_list = std::move(list); res.m_pos = std::move(pos); return res; } ListRange operator[](int u) { return ListRange{ m_list.begin() + m_pos[u], m_list.begin() + m_pos[u+1] }; } ConstListRange operator[](int u) const { return ConstListRange{ m_list.begin() + m_pos[u], m_list.begin() + m_pos[u+1] }; } int size() const { return m_n; } int fullSize() const { return (int)m_list.size(); } }; } // namespace nachia namespace nachia{ std::vector BipertiteMatching(int N1, int N2, const std::vector>& edges){ std::vector R(N2, -1); std::vector L(N1, -1); auto E = CsrArray::Construct(N1, edges); while(true){ std::vector bfs, dist(N1, -1), P(N1, -1); for(int i=0; i= maxD) break; for(int e : E[p]) if(L[p] != e){ if(R[e] >= 0){ if(dist[R[e]] < 0){ dist[R[e]] = dist[p] + 1; P[R[e]] = p; bfs.push_back(R[e]); } } else maxD = dist[p]; } } if(maxD > N1) break; std::vector I(N1, 0); for(int s=0; s= 0){ if(I[p] == E[p].size()){ p = P[p]; continue; } int q = E[p][I[p]++]; int r = R[q]; if(r == -1){ p2 = q; break; } if(dist[r] != dist[p] + 1) continue; P[r] = p; p = r; } if(p < 0) continue; while(p >= 0){ R[p2] = p; std::swap(L[p], p2); p = P[p]; } } } std::vector ans; for(int i=0; i<(int)edges.size(); i++){ auto& e = edges[i]; if(L[e.first] == e.second){ L[e.first] = -1; ans.push_back(i); } } return ans; } } // namespace nachia void testcase(){ ll N; cin >> N; V T(N); REP(i,N) cin >> T[i]; if(N%2 == 1){ cout << "-1\n"; return; } V mapping; V> conc(N); REP(i,N){ conc[i] = concrete(T[i], N); for(auto& a : conc[i]) mapping.push_back(a); } REP(i,N) if(conc[i].empty()){ cout << "-1\n"; return; } sort(mapping.begin(), mapping.end()); mapping.erase(unique(mapping.begin(), mapping.end()), mapping.end()); V> sha; REP(i,N) for(auto& a : conc[i]) sha.push_back({i,lower_bound(mapping.begin(), mapping.end(), a) - mapping.begin()}); auto mch = nachia::BipertiteMatching(N, mapping.size(), sha); V ch(N, -1); for(auto a : mch) if(a >= 0) ch[sha[a].first] = sha[a].second; REP(i,N) if(ch[i] < 0){ cout << "-1\n"; return; } REP(i,N) cout << mapping[ch[i]] << "\n"; } int main(){ cin.tie(0)->sync_with_stdio(0); testcase(); return 0; }