题目背景

合法括号串的定义：

• () 是合法的；
• 如果 A 是合法的，那么 (A) 是合法的；
• 如果 A 和 B 是合法的，那么 AB 是合法的。

题目描述

给定一个长为 $N$ 的字符串 $S$，由 (，) 和 ] 组成。

整个字符串中有 $M$ 个 ]，其他全为左右括号。

现在得知可以用若干个 ) 来替换 ]，求一种通过替换 $S$ 中的 ] 得到合法括号串的做法。

输入格式

第一行两个整数 $N,M$ 代表字符串的长度与 ] 的个数。
接下来有若干行，每行最多 $72$ 个字符，总计 $N$ 个字符，代表字符串 $S$。

输出格式

如果无解，输出 0 并结束程序。
如果有解，首先输出一个 1，然后接下来 $M$ 行每行一个整数代表每一个 ] 要替换多少成个 )。

8 2
(((((])] 

1
3
1

提示

样例说明

对于样例 $1$，按照输入替换后得到的 $S$ 为 ((((()))))，为合法括号串。

数据规模与约定

对于 $100\%$ 的数据，$1 \le N \le 10^7$，$1 \le M \le 5 \times 10^6$，$M \le N$。

本题使用 Special Judge。

感谢 spj 提供者

说明

翻译自 BalticOI 2005 Day1 B Magic Parenthesis。