正则括号序列是可以变换为正确的算术序列的括号序列。例如:
- 括号序列“()()“和”(())" 是正则表达式(结果表达式是: "(1)+(1)“和”((1+1)+1)");
- 括号序列“)(", "(“和”)“不是。
给你 $$$n$$$ 括号序列 $$$s_1, s_2, \dots, s_n$$$ (不一定是正则)和偶数 $$$k$$$。您的任务是将它们全部分成几组,方式如下:
- 每个括号序列都属于一组;
- 对于每个组,都存在一个 常规 长度恰好为 $$$k$$$ 的括号序列,使得分配给该组的每个括号序列是 不是子字符串 它。
可以实现的最小组数是多少?如果对于任意数量的组都无法做到这一点,请报告。否则,打印组以及每个组的任何有效的常规括号序列。如果组数最少有多个答案,则打印其中任何一个。
输入
第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le n \le 50$$$;$$$2 \le k \le 50$$$;$$$k$$$ 是偶数)。
接下来的 $$$n$$$ 行的第 $$$i$$$ 行包含括号序列 $$$s_i$$$ ($$$2 \le |s_i| \le k$$$)。它仅由字符 ' 组成(' 和 ')'.
输出
如果无法按照规则将所有括号序列分组,则打印$$$-1$$$。
否则,在第一行打印尽可能小的组数$$$m$$$。然后,$$$m$$$ 数据块应该如下:
- 每个块的第一行应包含长度为 $$$k$$$ 的常规括号序列。
- 第二行应包含一个整数 $$$g$$$ — 当前组中括号序列的数量。
- 第三行应包含从 $$$1$$$ 到 $$$n$$$ 的 $$$g$$$ 整数 - 属于当前组的括号序列的索引。
这些括号序列都不应该是所选常规括号序列的子字符串。从 $$$1$$$ 到 $$$n$$$ 的每个索引都应该属于一组。
如果存在多个最小 $$$m$$$ 的答案,请打印其中任何一个。
示例
输入复制
3 6)))((((())
输出复制
1 (()()) 3 1 2 3
输入复制
4 6(()()(())((((((
输出复制
2 (())() 1 2 ()()() 3 1 4 3
输入复制
2 6())(
输出复制
-1