Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 2704
Brackets

Time Limit: 2 Seconds      Memory Limit: 65536 KB

Given a string consisting of brackets of two types find its longest substring that is a regular brackets sequence.

Input

There are mutiple cases in the input file.

Each case contains a string containing only characters ‘(’ , ‘)’ , ‘[’ and ‘]’ . The length of the string does not exceed 100,000.

There is an empty line after each case.

Output

Output the longest substring of the given string that is a regular brackets sequence.

There should be am empty line after each case.

Sample Input

([(][()]]()

([)]

Sample Output

[()]



Source: Andrew Stankevich's Contest #10
Submit    Status