Longest Valid Parentheses Subsequence

You are given a string s that contains a mixture of letters and bracket characters. The bracket characters include the following pairs:

• ( )
• { }
• [ ]
• < >

Your task is to remove the minimum number of invalid bracket characters so that the remaining sequence (keeping the original order) forms a valid bracket sequence. A valid sequence is defined by the following criteria:

For every opening bracket c there must be a corresponding closing bracket c', where the pairs satisfy the relation $$ c' = \text{pairs}(c)$$ for the mapping $$ \{ ( : ),\; { : },\; [ : ],\; \}.$$

The resulting string should consist only of the bracket characters (i.e. ignore all non-bracket characters in the final output) and must be the longest valid subsequence obtainable by such removals.

For example:

• Input: a{b[ce]f}g produces Output: {[]}.
• Input: {(a)b]c produces Output: ().

inputFormat

The input consists of a single line containing the string s. The string may include letters and bracket characters.

outputFormat

Output a single line containing the longest valid parentheses subsequence (which is composed only of the bracket characters).

## sample

a{b[ce]f}g

{[]}