P7269 [BalticOI 2005] Magic Parenthesis (Day1)

Definition of a valid parenthesis string: - `()` is valid. - If `A` is valid, then `(A)` is valid. - If `A` and `B` are valid, then `AB` is valid.

Given a string $S$ of length $N$, consisting of `(`, `)`, and `]`. There are $M$ `]` in the whole string, and all other characters are left and right parentheses. Now you are allowed to replace each `]` with some number of `)` characters. Find a way to obtain a valid parenthesis string after replacing all `]` in $S$.

The first line contains two integers $N, M$, representing the length of the string and the number of `]`. The next several lines each contain at most $72$ characters, with a total of $N$ characters, representing the string $S$.

If there is no solution, output `0` and terminate the program. If there is a solution, first output `1`, then output $M$ lines. Each line contains one integer, representing how many `)` characters the corresponding `]` should be replaced with.

#### Sample Explanation For sample $1$, after performing the replacements as in the input, the resulting $S$ is `((((()))))`, which is a valid parenthesis string. #### Constraints For $100\%$ of the testdata, $1 \le N \le 10^7$, $1 \le M \le 5 \times 10^6$, and $M \le N$. **This problem uses Special Judge.** Thanks to the SPJ provider @[tiger2005](https://www.luogu.com.cn/user/60864). #### Notes Translated from [BalticOI 2005 Day1 B Magic Parenthesis](https://boi.cses.fi/files/boi2005_day1.pdf). Translated by ChatGPT 5