Magic Parenthesis

In the LISP programming language, everything is written inside balanced parentheses (LIKE THIS). As a result, LISP code sometimes contains long runs of closing parentheses )))...). Making the number of closing parentheses ) match the number of opening parentheses ( exactly is tedious and error-prone.

To avoid such mistakes, some LISP dialects add a magic closing parenthesis ], which stands for one or more closing parentheses ) — as many as are needed to balance the currently open parentheses. The compiler must then work out how many closing parentheses ) each magic parenthesis ] actually represents.

You are given a string made of opening parentheses (, closing parentheses ), and magic parentheses ]. Determine, for each magic parenthesis, how many closing parentheses ) it stands for so that the whole string becomes balanced.

The first line contains two integers N and M (0 ≤ N ≤ 10000000, 0 ≤ M ≤ 5000000) separated by a space. N is the length of the bracket string, and M is the number of magic parentheses in it.

Starting from the second line, the bracket string of length N is given. It consists only of the characters (, ), and ], and the character ] appears exactly M times (M ≤ N). For readability the string may be split across several lines of at most 72 characters each; concatenate them, ignoring the line breaks, to obtain the string.

On the first line, print 1 if the string can be balanced, or 0 if it cannot. (For example, a string consisting of a single magic parenthesis ] can never be balanced.)

If you printed 0, print nothing more.

If you printed 1, print M additional lines. Each magic parenthesis ] must stand for at least one closing parenthesis. The i-th of these lines contains C_i ≥ 1, the number of closing parentheses ) that the i-th magic parenthesis (in left-to-right order) represents.

Several assignments may balance the same string. In that case, print the lexicographically largest sequence C_1, C_2, …, C_M: make C_1 as large as possible, then C_2 as large as possible, and so on.

Consider the first example, a string of 8 characters that contains 2 magic parentheses. One way to balance it lets the first magic parenthesis stand for 3 closing parentheses and the second for 1, turning the string into the fully balanced ((((())))). Because larger earlier values are preferred, this 3, 1 assignment is exactly the lexicographically largest one.