题目描述

一个括号序列是一个只包含字符 "("、")"、"[" 和 "]" 的字符串。

一个合法的括号序列，是指通过在原始括号序列的字符间插入 "1" 和 "+"，能够变成一个合法算术表达式的括号序列。例如，括号序列 "()[]"、"([])" 都是合法的（插入后得到的表达式为 "(1)+[1]"、"([1+1]+1)"），而 "](" 和 "[" 不是合法括号序列。空串根据定义是一个合法括号序列。

字符串 $s$ 的子串 $s[l \ldots r]\ (1 \leq l \leq r \leq |s|)$（其中 $|s|$ 是 $s$ 的长度）表示为 $s_{l}s_{l+1}\ldots s_{r}$。根据定义，空串是任意字符串的子串。

现在给定一个括号序列（不一定合法），请找出它的一个子串，使得它是一个合法括号序列，并且包含尽可能多的左中括号「[」。

输入格式

输入仅一行，包含一个只由 "("、")"、"[" 和 "]" 组成的括号序列。保证字符串非空且长度不超过 $10^{5}$。

输出格式

第一行输出一个整数，表示所选序列中「[」的最大数量。
第二行输出这个最优的合法括号序列。如果有多种最优解，输出任意一种均可。

说明/提示

由 ChatGPT 5 翻译

样例

([])

1
([])

(((

0