题目描述

对一个由 (、)、[、] 四种括号组成的字符串，求出其中最长的括号匹配子串。具体来说，满足如下条件的字符串成为括号匹配的字符串：

• ()、[] 是括号匹配的字符串。

• 若 A 是括号匹配的串，则 (A)、[A] 是括号匹配的字符串。

• 若 A、B 都是括号匹配的字符串，则 AB 也是括号匹配的字符串。

例如：()、[]、([])、()() 都是括号匹配的字符串，而 ][、[(]) 则不是。

字符串 $A$ 的子串是指由 $A$ 中连续若干个字符组成的字符串。

例如，A、B、C、ABC、CAB、ABCABC 都是字符串 ABCABC 的子串，而 D、BA、ACB 则不是。空串是任何字符串的子串。

输入格式

输入一行，为一个仅由 ()[] 组成的非空字符串。

输出格式

输出一行，为最长的括号匹配子串。若有相同长度的子串，输出在原字符串内出现位置靠前的子串。

([(][()]]()

[()]

())[]

()

提示

数据范围

记 $n$ 为输入字符串的长度。

对于 $20\%$ 的数据，$n \le {10}^2$。

对于 $50\%$ 的数据，$n \le {10}^4$。

对于 $100\%$ 的数据，$n \le {10}^6$。