描述

这里有一个非常长的字符串，它由大、中、小括号(英文)组成，你的任务就是找出最长和谐子字符串。

和谐字符串的定义如下：
1 . 这个子串是连续的
2 . 在这个子串中，左右括号的数量相等，每一个左括号都对应有一个与其性质相同的右括号与其配对，
并且每对括号中间或者没有东西，或者也是一个和谐子串。

如果有多个相等长度的，请输出最靠左的一个。

格式

输入格式

一个长度不超过\(5 \times 10^6\)的字符串\(s\)。

输出格式

最长的和谐子字符串

样例1

样例输入1

{}}[()()]

样例输出1

[()()]

限制

各个测试点1s,256MB
对于30%的数据，保证\(1 \leq |s| \leq 5000\)。
对于100%的数据，保证\(1 \leq |s| \leq 5 \times 10^6\)。

提示

注意所有括号均为英文输入
为了让大家理解和谐字符串，在这里举几个例子：

序号	例子	是否和谐	说明
\(1\)	{}[][]]	No	左括号和与右括号数量不相等
\(2\)	{{]}	No	不能让左括号和右括号一一匹配
\(3\)	{{[(])}}	No	可以让左右括号一一匹配，但成对括号当中有不和谐字符串
\(4\)	{{{}}}	Yes	符合要求
\(5\)	()[]	Yes	符合要求