#include #include using namespace std; using ll = long long; bool check(string candidate, string t) { for (int i = 0; i < candidate.size(); i++) { if (t[i] != '.' && candidate[i] != t[i]) return false; } return true; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N; cin >> N; vector T(N); for (int i = 0; i < N; i++) { cin >> T[i]; } if (N % 2 == 1) { cout << "-1" << endl; return 0; } vector candidates; auto f = [&](auto self, string body, int depth) -> void { if (body.size() == N) { if (depth == 0) candidates.push_back(body); } else { if (depth > 0) self(self, body + ")", depth - 1); if (depth < N / 2) self(self, body + "(", depth + 1); } }; f(f, "", 0); if (candidates.size() < N) { cout << "-1" << endl; return 0; } int C = candidates.size(); int source = 0; int sink = 1; int candHead = 2; int tHead = candHead + C; atcoder::mf_graph g(2 + C + N); for (int i = 0; i < C; i++) { g.add_edge(source, candHead + i, 1); } for (int i = 0; i < N; i++) { g.add_edge(tHead + i, sink, 1); } for (int i = 0; i < C; i++) { for (int j = 0; j < N; j++) { if (check(candidates[i], T[j])) { g.add_edge(candHead + i, tHead + j, 1); } } } int maxflow = g.flow(source, sink); if (maxflow != N) { cout << "-1" << endl; return 0; } auto edges = g.edges(); vector S(N); for (int i = 0; i < edges.size(); i++) { if (edges[i].from == source || edges[i].to == sink) continue; if (edges[i].flow == 1) { S[edges[i].to - tHead] = candidates[edges[i].from - candHead]; } } for (int i = 0; i < N; i++) { cout << S[i] << endl; } }