括号序列是一个字符串,仅包含字符“(”、“)”、“[”和“]”。
正确的括号序列是通过在序列的原始字符之间插入字符“1”和“+”可以将括号序列转化为正确的算术表达式。例如,括号序列“()[]”、“([])”是正确的(结果表达式为:“(1)+[1]”、“([1+1]+1)”),而“](”和“[”则不正确。根据定义,空字符串是正确的括号序列。
字符串 s = s1s2... s|s| 的子串 s[l... r] (1 ≤ l ≤ r ≤ |s|) (其中 |s| 是字符串 s 的长度)是字符串 slsl + 1... sr。根据定义,空字符串是任何字符串的子字符串。
给你一个括号序列,不一定正确。找到它的子字符串,该子字符串是正确的括号序列并且包含尽可能多的左方括号“[”。
输入
第一行也是唯一一行包含字符串形式的括号序列,仅包含字符“(”、“)”、“[”和“]”。保证字符串非空且长度不超过105个字符。
输出
在第一行中打印一个整数 - 所需括号序列中括号 «[» 的数量。在第二行中打印最佳序列。如果有多个最佳解决方案,则打印其中任何一个。
示例
输入 #1
([])
输出 #1
1 ([])
输入 #2
(((
输出 #2
0