← 返回题目列表

Codeforces · 223/A

A. 括号顺序

中文机器翻译题面 查看原题

括号序列是一个字符串,仅包含字符“(”、“)”、“[”和“]”。

正确的括号序列是通过在序列的原始字符之间插入字符“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