Valid Parentheses

Given a string s consisting solely of the characters '(', ')', '{', '}', '[' and ']', determine if the string is valid. The string is considered valid if and only if:

• Every open bracket is closed by the same type of bracket.
• Open brackets are closed in the correct order.

In mathematical notation, the conditions for a valid string can be expressed as follows:

\(\forall\, s \in \{(, ), {, }, [, ]\} : \text{valid}(s)\) if and only if the pairing follows the above rules.

For example, if s = "()[]{}", then the output is True whereas if s = "([)]", then the output is False.

inputFormat

A single line string s containing only the characters '(', ')', '{', '}', '[' and ']'. The input is provided via stdin.

outputFormat

Output exactly one line: 'True' if the bracket string is valid, otherwise 'False'. The output is produced on stdout.## sample

()

True