Problem Description

Given a string consisting of parentheses (, ), [, and ], find the longest substring that is a valid parenthesis matching. Specifically, a string is considered a valid parenthesis matching if it meets the following conditions:

1. (), [] are valid parenthesis matchings.
2. If A is a valid parenthesis matching, then (A) and [A] are also valid parenthesis matchings.
3. If A and B are valid parenthesis matchings, then AB is also a valid parenthesis matching.

For example, (), [], ([]), and ()() are valid parenthesis matchings, while ][, [(]) are not.

A substring of string A is a string consisting of consecutive characters from A.

For example, A, B, C, ABC, CAB, and ABCABCd are all substrings of ABCABC. The empty string is a substring of any string.

Input Format

Input consists of a single line, which is a non-empty string composed only of parentheses (, ), [, and ].

Output Format

Output consists of a single line, which is the longest valid parenthesis matching substring. If there are multiple substrings of the same length, output the one that appears first.

Sample Input and Output

Sample Input #1

([(][()]]()

Sample Output #1

[()]

Sample Input #2

())[]

Sample Output #2

()

Notes

Data Range

• For 20% of the data, the string length is ≤ 100.
• For 50% of the data, the string length is ≤ 10,000.
• For 100% of the data, the string length is ≤ 1,000,000.

见题面 Input 部分

见题面 Output 部分