现在 Kuroni 已经 10 岁了,他是一个大男孩了,不再喜欢整数数组作为礼物了。今年他想要一个 Bracket 序列作为生日礼物。更具体地说,他想要一个如此复杂的括号序列,无论他如何努力,他都无法删除一个简单的子序列!
如果 $$$n$$$ 字符“(”或“)”长度为偶数且为正数,并且第一个 $$$\frac{n}{2}$$$ 字符为“(”,最后一个 $$$\frac{n}{2}$$$ 字符为“)”,则我们称由 $$$n$$$ 字符“(”或“)”组成的字符串是简单字符串。例如,字符串 () 和 (()) 很简单,而字符串 )( 和 ()() 则不简单。
Kuroni 将得到一个由字符 '(' 和 ')' 组成的字符串(给定的字符串不一定很简单)。操作包括选择形成简单字符串的字符串的字符子序列并从字符串中删除该子序列的所有字符。请注意,该子序列不必是连续的。例如,他可以将操作应用于字符串')()(()))',以选择粗体字符的子序列,因为它形成一个简单的字符串'(())',从字符串中删除这些粗体字符并得到'))()'。
Kuroni 必须对字符串执行尽可能少的操作,这样就不能对剩余的字符串执行更多操作。结果字符串不必为空。
由于给定的字符串太大,Kuroni 无法弄清楚如何最小化操作次数。你能帮他代替吗?
字符序列 $$$a$$$ 是字符串 $$$b$$$ 的子序列,如果 $$$a$$$ 可以通过删除几个(可能是零个或全部)字符从 $$$b$$$ 获得。
输入
输入的唯一行包含一个由字符“(”和“)”组成的字符串 $$$s$$$ ($$$1 \le |s| \le 1000$$$),其中 $$$|s|$$$ 是 $$$s$$$ 的长度。
输出
在第一行中,打印一个整数 $$$k$$$ — 您必须应用的最少操作数。然后,按以下格式打印描述操作的 $$$2k$$$ 行:
对于每个操作,打印一行包含整数 $$$m$$$ — 您将删除的子序列中的字符数。
然后,打印一行包含 $$$m$$$ 整数 $$$1 \le a_1 < a_2 < \dots < a_m$$$ — 您要删除的字符的索引。所有整数必须小于或等于当前字符串的长度,并且相应的子序列必须形成一个简单字符串。
如果存在多个具有最小 $$$k$$$ 的有效操作序列,则可以打印其中任何一个。
示例
输入 #1
(()((
输出 #1
1 2 1 3
输入 #2
)(
输出 #2
0
输入 #3
(()())
输出 #3
1 4 1 2 5 6
注意
在第一个示例中,字符串是 '(()(('。所描述的操作对应于删除粗体子序列。生成的字符串是 '(((',并且不能对其执行更多操作。另一个有效答案是选择索引 $$$2$$$ 和 $$$3$$$,这会产生相同的最终字符串。
在第二个示例中,已经无法执行任何操作。