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

[()]

include

include

include

include

using namespace std;

class Substr{
private:
int from;
int length;
string s;
bool ispair(char a, char b)
{
if(a ==’(‘ && b == ‘)’)
return true;
else if(a == ‘[‘ && b == ‘]’)
return true;
else
return false;
}
void calculate()
{
int max = 0;
int len = 0;
const char* p = this->s.c_str();
stack vc;

    do
    {
        if(!vc.empty() && ispair(vc.top(),*p)){
            vc.pop();
            len++;
        } else {
            if(len > max){
                max = len;
                from = p-this->s.c_str();
                length = len*2;
                from -= length;
            }
            len = 0;
            vc.push(*p);
        }
    }while(*p++);
}

public:
Substr(string str)
{
s = str;
from = 0;
length = 0;
}
void print()
{
calculate();
cout<<s.substr(from, length)<<endl;
cout<>s){
Substr ss(s);
ss.print();
}
return 0;
}