Valid Parentheses Checker

You are given a string s consisting of the characters '(', ')', '{', '}', '[' and ']'. Your task is to determine whether the input string is valid. A string is valid if:

1. Every opening bracket has a corresponding closing bracket of the same type.
2. Opening brackets must be closed in the correct order.

Formally, a string s is valid if it can be transformed into a correct bracket sequence. In mathematical notation, if we denote the string as \( s \), then it is valid if:

$$ \text{valid}(s) = \begin{cases} \text{True} & \text{if } s = \epsilon \text{ or } s = (A), [A], \{A\} \text{ for some valid } A, \\ \text{False} & \text{otherwise.} \end{cases} $$

Note that an empty string is also considered valid.

inputFormat

Input is given from standard input. The input consists of a single line containing a non-empty string formed by the characters '(', ')', '{', '}', '[' and ']'.

outputFormat

Output to standard output a single line: either 'True' if the string is a valid parentheses sequence or 'False' otherwise.## sample

()

True