Valid Bracket String

Given a string S containing only the characters ('), ')', '[', ']', '{' and '}', determine if the string is valid.

A string is considered valid if and only if it satisfies one of the following conditions:

• Empty string: The string is empty.
• Concatenation: The string can be split into two valid strings, i.e. if A and B are both valid, then the concatenation AB is valid.
• Enclosed string: The string can be written in the form \( (A) \), \( [A] \), or \( \{A\} \) where \(A\) is a valid string.

For instance, () and {[()]} are valid, but (] and ( are not.

inputFormat

The input consists of a single line containing a string S composed exclusively of the characters ('), ')', '[', ']', '{', and '}'.

outputFormat

Output a single line: True if the string S is valid according to the above rules, otherwise output False.

()

True