Replacing Brackets to Form a Valid Parentheses Sequence

You are given a string (S) of length (N) consisting of the characters '(', ')' and ']'. In this string, there are (M) occurrences of ']' and all other characters are either '(' or ')'. You are allowed to replace each occurrence of ']' with a positive number of closing parentheses (i.e. ')'). Your task is to choose the number of ')' characters for each ']' such that after all replacements, the resulting string becomes a valid parentheses sequence.

A parentheses sequence is valid if and only if:

1. In every prefix of the string, the number of '(' is greater than or equal to the number of ')'.
2. The total number of '(' equals the total number of ')' in the entire sequence.

If a valid replacement exists, output the resulting string on the first line, followed by the number of ')' that replaced each ']' in the order of appearance in (S). If no valid replacement exists, output a single line containing 0.

Note: All mathematical formulas are written in (\LaTeX) format.

inputFormat

The input consists of two lines:

1. An integer \(N\) representing the length of the string \(S\).
2. A string \(S\) of length \(N\) composed of the characters `'('`, `')'` and `']'`.

outputFormat

If a valid replacement exists:

1. The first line should contain the resulting valid parentheses sequence after replacing each `']'`.
2. Then, for each occurrence of `']'` in \(S\) (in order), output a line with the positive integer representing the number of closing parentheses used to replace that `']'`.

If no valid replacement exists, output a single line containing 0.

sample

4
((])

(())
1