Valid Parentheses Checker

You are given a string S consisting of characters among parentheses (), square brackets [], and curly braces {}. Determine whether the string is valid. A string is considered valid if:

• Every opening symbol has a corresponding closing symbol of the same type.
• The parentheses are properly nested.

In mathematical terms, if we denote the set of valid matching as \(\{ ( , )\}, \{[ , ]\}, \{\{ , \}\} \), then a string \(S\) is valid if every prefix of \(S\) contains no more closing symbols than opening symbols and the total count of opening and closing symbols match.

The input will be read from stdin and the output should be printed on stdout.

inputFormat

The input consists of a single line containing the string S. The string may be empty, in which case it is considered valid.

Note: Only the characters '(', ')', '[', ']', '{', and '}' are allowed. Any other character should be considered invalid.

outputFormat

Print True if the string S is valid and properly nested; otherwise, print False.

()

True