Description

A regular brackets sequence is defined below:

1. An EMPTY sequence is a regular brackets sequence;

2. If R is a regular brackets sequence, then [R] (R) are both regular brackets sequences;

3. If R is a regular brackets sequence, then []R ()R R[] R() are regular brackets sequences.

4. If R1 and R2 are a regular brackets sequences, then R1R2 is a regular brackets sequence.

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

Input

There are multiple cases in the input file. Process to the end of file.

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

There is an empty line after each case.

Output

Output the longest substring of the given string that is a regular brackets sequence in one line. If there are more than one answer, just output the first one. If there is no such substring, just output an empty line. Output an empty line after each test case.

Sample

Input

([(][()]]()

([)]

Output

[()]

Source: ycc