A bracket sequence is a string, containing only characters "(", ")", "[" and "]".

A correct bracket sequence is a bracket sequence that can be transformed into a correct arithmetic expression by inserting characters "1" and "+" between the original characters of the sequence. For example, bracket sequences "()[]", "([])" are correct (the resulting expressions are: "(1)+[1]", "([1+1]+1)"), and "](" and "[" are not. The empty string is a correct bracket sequence by definition.

A substring s[l... r] (1 ≤ l ≤ r ≤ |s|) of string s = s1s2... s|s| (where |s| is the length of string s) is the string slsl + 1... sr. The empty string is a substring of any string by definition.

You are given a bracket sequence, not necessarily correct. Find its substring which is a correct bracket sequence and contains as many opening square brackets «[» as possible.

Input

The first and the only line contains the bracket sequence as a string, consisting only of characters "(", ")", "[" and "]". It is guaranteed that the string is non-empty and its length doesn't exceed 105 characters.

Output

In the first line print a single integer — the number of brackets «[» in the required bracket sequence. In the second line print the optimal sequence. If there are more than one optimal solutions print any of them.

Examples

input

Copy

([])

output

Copy

1
([])

input

Copy

(((

output

Copy

0

栈模拟

匹配 [  ]   和  （ ）     ，将" [ " 或"("  入栈 (是把它在字符串中的相应位置入栈，方便分段查询），若匹配到相应的括号，则出栈，否则则压入。最后若栈中还有元素，即为区间断点，假设有m个元素，则分成m+1个区间。下边是贴的别人的代码。

AC Code：

#include <cstdio>
#include <map>
#include <stack>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
    #ifndef ONLINE_JUDGE
   freopen("input.txt","r",stdin);
    #endif // ONLINE_JUDGE
	map<char,int> m;
	m['('] = 1;//匹配方便
	m[')'] = -1;
	m['['] = 2;
	m[']'] = -2;
	char str[100000+22];
	int l;
	int ans;
	while (~scanf ("%s",str))
	{
		l = strlen(str);
		stack<int> s;
		ans = 0;
		for (int i = 0 ; i < l ; i++)
		{
			if (m[str[i]] == 1 || m[str[i]] == 2)//将左括号入栈
				s.push(i);
			else if (s.empty())
				s.push(i);
			else if (m[str[i]] + m[str[s.top()]] == 0)		//可以配对，弹出
				s.pop();
			else		//不能配对，压入
				s.push(i);
		}

		if (s.empty())		//全部完成匹配
		{
			for (int i = 0 ; i < l ; i++)
				if (m[str[i]] == 2)
					ans++;
			printf ("%d\n%s\n",ans,str);
		}
		else//分区间查询
		{
			int st,endd;
			int ans_st,ans_endd;		//满足条件的开始于结束位置
			int ant;
			s.push(l);
			while (s.size() != 1)
			{
				endd = s.top() - 1;
				s.pop();
				st = s.top() + 1;
				ant = 0;
				for (int i = st ; i <= endd ; i++)
					if (m[str[i]] == 2)
						ant++;
				if (ant > ans)
				{
					ans = ant;
					ans_st = st;
					ans_endd = endd;
				}
			}
			st = 0;
			endd = s.top() - 1;
			ant = 0;
			for (int i = st ; i <= endd ; i++)
				if (m[str[i]] == 2)
					ant++;
			if (ant > ans)
			{
				ans = ant;
				ans_st = st;
				ans_endd = endd;
			}
			if (ans)
			{
				printf ("%d\n",ans);
				for (int i = ans_st ; i <= ans_endd ; i++)
					printf ("%c",str[i]);
				printf ("\n");
			}
			else
				printf ("0\n\n");
		}
	}
	return 0;
}

然后我自己写一遍

AC Code：
 

#include<iostream>
#include<iomanip>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<string>
#include<algorithm>
#include<vector>
#include<map>
#include<stack>
#include<queue>
#include<deque>
#include<set>
#include<bitset>
#include<cctype>
#define LL long long
#define maxn (LL)1e5
#define INF 0x3f3f3f3f
const double eps = 0.0000001;
using namespace std;
inline int sgn(double x) {
    return (x > eps) - (x < -eps);
}
map<char,int> st;
char c[100005];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    #ifndef ONLINE_JUDGE
   //freopen("input.txt","r",stdin);
    #endif // ONLINE_JUDGE
    st['('] = 1;
    st[')'] = -1;
    st['['] = 2;
    st[']'] = -2;
    cin>>(c+1);
    int l = strlen(c+1);
    stack<int> s;
    int k = 0;
    for(int i =1;i<=l;++i)
    {
        if(c[i]=='('||c[i]=='[')  {s.push(i);if(c[i]=='['){k++;}}
        else if(s.empty()) s.push(i);
        else if(st[c[i]]+st[c[s.top()]]==0) s.pop();
        else s.push(i);
    }
    if(s.empty()) {
        cout<<k<<endl;
        cout<<(c+1);
        return 0;
    }
    else {
        s.push(l+1);
        int star, end;
        int Left,right;
        int ans = 0;
        while(s.size()!=1)
        {
            right = s.top()-1;
            s.pop();
            Left = s.top()+1;
            int res = 0;
            for(int i = Left;i<=right;++i)
            {
                if(c[i] == '[')  res++;
            }
            if(res>ans){
                ans = res;
                star = Left;
                end = right;
            }
        }
        right = s.top()-1;
        int res = 0;
        for(int i = 1;i<=right;++i)
        {
            if(c[i] == '[') res++;
        }
        if(ans<res) {
            ans = res;
            star  = 1;
            end = right;
        }
        if(ans == 0) cout<<0<<endl;
        else {
            cout<<ans<<endl;
            for(int i = star;i<=end;++i)
                cout<<c[i];
            return 0;
        }
    }


}