LP.py

M = -10 ** 9 + 7
def _match(s, i, j):
    if s[i]=='{' and s[j]=='}':
        return 2
    if s[i]=='(' and s[j]==')':
        return 2
    if s[i]=='[' and s[j]==']':
        return 2
    return 0

def _out(s, _dp, i, j):
    if _dp[i][j]==0:
        return ''
    if i>=j:
       return ''
    for k in range(i,j):
        if _dp[i][j]==_dp[i][k]+_dp[k][j] and (_dp[i][k]>0 or _dp[j][k]>0):
            return _out(s, _dp, i, k)+_out(s, _dp, k, j)
    if _dp[i][j]==_dp[i+1][j-1]+2:
       return s[i]+_out(s,_dp, i+1, j-1)+s[j]
    return ''

def _lp(s):
    if s=="":
        return 0
    _dp=[[0 for _ in range(len(s))] for _ in range(len(s))]
    for l in range(len(s)-1, -1, -1):
        _dp[l][l]=0
        for r in range(l+1, len(s)):
            _dp[l][r]=max(_dp[l+1][r-1]+_match(s, l, r), max([_dp[l][k]+_dp[k][r] for k in range(l,r)]))
    return _dp[0][-1]>0, _dp

def lp(s):
    result, _dp = _lp(s)
    if result:
        return _out(s, _dp, 0, len(s)-1)
    else:
        return

s=input().rstrip()
print(lp(s))