题目描述

对于一个由(,),[,]括号组成的字符串，求出其中最长的括号匹配子串。

具体来说，满足如下条件的字符串成为括号匹配的字符串：

（1） (),[] 是括号匹配的字符串。

（2） 若A是括号匹配的串，则(A)或[A] 是括号匹配的字符串。

（3） 若A和B都是括号匹配的字符串，则A+B也是括号匹配的字符串。（这里的+是字符串的加法运算）。

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

字符串A的子串是指由A中连续若干个字符组成的字符串。例如：A,B,C,ABC,CAB,ABCCABC都是ABCABC的子串。空串是任何字符串的子串。

输入格式

输入一行，为一个仅由()[]组成的非空字符串。(括号都是英文输入法的括号)

输出格式

输出也仅有一行，为最长的括号匹配子串。若有相同长度的子串，输出位置靠前的子串。

input

【输入样例1】

([(][()]]()

output

【输出样例2】

[()]

input

【输入样例2】

())[]

output

【输出样例2】

()

数据规模与约定

【数据规模】

对于20%的数据，字符串长度<=100

对于50%的数据，字符串长度<=10,000

对于100%的数据，字符串长度<=1,000,000

时间限制：1s

空间限制：256MB