Description

Given a string consisting of the four brackets (, ), [ and ], find its longest bracket-matching substring. Specifically, a string is bracket-matching if it satisfies the following conditions:

• () and [] are bracket-matching strings.
• If A is a bracket-matching string, then (A) and [A] are bracket-matching strings.
• If A and B are both bracket-matching strings, then AB is also a bracket-matching string.

For example: ()、[]、([])、()() are bracket-matching strings, while ][ and [(]) are not.

A substring of string $A$ is a string formed by a consecutive block of characters from $A$.

For example, A、B、C、ABC、CAB、ABCABC are all substrings of the string ABCABC, while D、BA、ACB are not. The empty string is a substring of any string.

Input Format

Input consists of one line, a non-empty string composed only of ()[].

Output Format

Output one line: the longest bracket-matching substring. If there are multiple substrings with the same length, output the one that appears earlier in the original string.

([(][()]]()

[()]

())[]

()

Hint

Constraints

Let $n$ be the length of the input string.

For $20\%$ of the testdata, $n \le {10}^2$.

For $50\%$ of the testdata, $n \le {10}^4$.

For $100\%$ of the testdata, $n \le {10}^6$.

Translated by ChatGPT 5