Magic Parenthesis#3013
In the LISP programming language, everything is written inside balanced parentheses (LIKE THIS). This means that LISP code sometimes contains long stretches of closing parentheses ")))...)". It is very tedious for the LISP programmer to ensure that the number of closing parentheses ')' matches exactly the number of opening parentheses '('.
To prevent such syntax errors, some LISP dialects introduce a magic closing parenthesis ']' which substitutes one or more closing parentheses ')' as needed to properly balance the opening parentheses '('. In this case, the LISP compiler must determine how many closing parentheses ')' each magic parenthesis ']' actually represents. How can this be done?
Write a program that receives a string consisting of opening, closing, and magic parentheses, and for each occurrence of the magic parenthesis computes the number of closing parentheses it substitutes for. If there are multiple solutions, your program may output any one of them.
The first line contains two integers 0 \le N \le 10000000 and 0 \le M \le 5000000 separated by a space. The first value is the length of the input string. The second value is the number of magic closing parentheses in the string. The rest of the input, starting from the second line, gives the string of length , consisting of characters '(', ')', and ']'. The character ']' occurs exactly times (with M \le N). For convenience, this string is split into lines of at most characters each.
The first line contains an integer '0' or '1'. The value '0' means the input cannot be balanced (for example, the string consisting of a single magic parenthesis "]" obviously cannot be balanced). In this case there is no further output.
The value '1' means the input can be balanced. In this case, the output continues with additional lines.
The first additional line contains an integer C_1 \ge 1, which denotes how many closing parentheses ')' the first magic parenthesis ']' in the input string substitutes. The second additional line contains the corresponding value C_2 \ge 1 for the second magic parenthesis ']' in the input, and so on.
If there are many ways to balance the string, your program may output any one of them.
مثال 1
The example input describes a string with characters, including magic parentheses. The output demonstrates one way to balance this input: the first magic parenthesis corresponds to opening parentheses, and the second to opening parenthesis. In this way, the string is properly balanced, with the closing parentheses corresponding to magic parentheses highlighted.