Longest Beautiful Bracket Substring

Candela, a comic artist, has a quirky hobby of drawing brackets on paper. One morning, she drew a sequence consisting of three types of brackets: (), [], and {} with a total length of \(N\). The drawn sequence looks chaotic. Candela defines a bracket sequence to be beautiful if it satisfies the following rules:

1. The empty sequence is beautiful.
2. If a sequence \(A\) is beautiful, then \((A)\), \([A]\), and \({A}\) are also beautiful.
3. If sequences \(A\) and \(B\) are beautiful, then their concatenation \(AB\) is also beautiful.

For example, [(){}]() is beautiful, whereas )([{)[}](` is not.

Candela now wants to find a contiguous segment (substring) of her drawn bracket sequence that is beautiful and has the maximum possible length. If there are multiple answers, output the first one. Note that the empty string is also considered beautiful, so if no non-empty beautiful segment exists, output an empty string.

inputFormat

The input consists of a single line containing a string of characters. Each character is one of the following: (, ), [, ], {, or }.

outputFormat

Output the longest contiguous substring that forms a beautiful (balanced) bracket sequence. If there are multiple substrings with the maximum length, output the one that appears first. If no non-empty valid substring exists, output an empty string.

sample

()[]{}

()[]{}