题目描述

Deni 非常喜欢合法括号表达式。某天她想出了这样一个游戏：

她先写下一个长度为 N 的括号串，只包含圆括号 '(' 和 ')'。
然后她任意选择一个整数 K（1 <= K <= N），把这个括号串划分成 K 个非空连续部分。

接下来，对于每一部分，她都会计算其中最长合法括号子序列的长度。
这里“子序列”指的是：从原序列中删除若干个元素（可以为 0 个，且删除位置不要求连续）后得到的序列。

最后，她把这 K 个部分各自的最长合法括号子序列长度加起来，得到一个总和。

Deni 想知道：应如何划分这串括号，使这个总和最小。
请你编写程序 braces 来解决这个问题。

由于最优划分可能不唯一，她还提出了额外要求：

• 在所有最优划分中，先输出最后一段最长的那一种；
• 如果仍有多种，则比较倒数第二段长度，选择更长者；
• 若还不唯一，则继续从后往前比较每一段长度，始终优先选择更长的。

此外，她还希望输出另一个极端方案：

• 在所有最优划分中，再输出最后一段最短的那一种；
• 如仍不唯一，则比较倒数第二段，选择更短者；
• 若还不唯一，则继续从后往前比较每一段长度，始终优先选择更短的。

输入格式

• 第一行输入一个仅由 '(' 与 ')' 组成的字符串；
• 第二行输入整数 K。

输出格式

第一行输出最小总和。

接下来输出 K 行，表示在所有最优划分中：

• 最后一段尽可能长的那个方案；
• 若不唯一，则倒数第二段尽可能长；
• 依此类推。

每一行格式为：

i, [beg, end], num: pos1 pos2 ... posnum

含义如下：

• 第 i 段对应原串中的区间 [beg, end]；
• 该段的最长合法括号子序列长度为 num；
• pos1, pos2, ..., posnum 是这个子序列所选括号在原串中的位置，满足：

beg <= pos1 < pos2 < ... < posnum <= end

再接下来输出 K 行，表示在所有最优划分中：

• 最后一段尽可能短的那个方案；
• 若不唯一，则倒数第二段尽可能短；
• 依此类推。

数据范围

• 3 <= N <= 1000
• 3 <= K <= 200

子任务

只有通过某子任务的全部测试，才能获得该子任务分数。

样例 1

输入 1

()()
3

输出 1

0

1, [1,1], 0:
2, [2,3], 0:
3, [4,4], 0:

1, [1,1], 0:
2, [2,3], 0:
3, [4,4], 0:

样例解释 1

把原串划分成下面三个部分：

(
)(
)

对于每一段，都找不到合法括号子序列，因此总和为 0。

样例 2

输入 2

(()(()
2

输出 2

2

1, [1, 2], 0:
2, [3, 6], 2: 5 6

1, [1, 5], 2: 2 3
2, [6, 6], 0:

样例解释 2

本例中恰好有两种划分方式能够得到最优答案 2。

• 第一种划分的第二段更长，因此它先输出；
• 第二种划分随后输出。

例如，若划分为 [1,3] 与 [4,6]，则答案为 4，因为两段中都存在长度为 2 的合法括号子序列。
若划分为 [1,1] 与 [2,6]，答案同样为 4，因为后一段中存在长度为 4 的合法括号子序列 ()(()) 的一个子序列（题面原文举例为由第 1, 2, 4, 5 个括号组成，对应到该段中的相对位置）。