Description

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$.

Input Format

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$.

Output Format

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.

8 2
(((((])] 

1
3
1

Hint

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

Notes

Translated from BalticOI 2005 Day1 B Magic Parenthesis.

Translated by ChatGPT 5