题目描述

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

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

2.若 $A$ 是括号匹配的串，则 ($A$) , [$A$] 是括号匹配的字符串。

3.若 $A$ , $B$ 是括号匹配的字符串，则 $AB$ 也是括号匹配的字符串。

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

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

例如，A , B , C , ABC , CAB , ABCABC 都是 ABCABC 的子串。空串是任何字符串的子串。

（上一行原文中最后一个子串样例有误，为 ABCABCd，应为 ABCABC）

输入格式

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

输出格式

（无误）

说明/提示

【数据范围】

对 $20\%$ 的数据，字符串长度 $\le100$.

对 $50\%$ 的数据，字符串长度 $\le10000$.

对 $100\%$的数据，字符串长度 $\le1000000$.

---

---

### 题目描述

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

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

2.若 $A$ 是括号匹配的串，则 `(`$A$`)` , `[`$A$`]` 是括号匹配的字符串。

3.若 $A$ , $B$ 是括号匹配的字符串，则 $AB$ 也是括号匹配的字符串。

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

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

例如，`A` , `B` , `C` , `ABC` , `CAB` , `ABCABC` 都是 `ABCABC` 的子串。空串是任何字符串的子串。


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

### 说明/提示
【数据范围】

对 $20\%$ 的数据，字符串长度 $\le100$.

对 $50\%$ 的数据，字符串长度 $\le10000$.

对 $100\%$的数据，字符串长度 $\le1000000$.