Valid Parentheses

Given a string s that consists of only the characters ('), '{'}', and '[' and ']', determine if the input string is valid. A string is considered valid if:

• It is empty, or
• It can be written as a concatenation of two valid strings, i.e. A B, or
• It can be written in the form (A), [A] or {A}, where A is a valid string.

In other words, a valid string satisfies the following recursive definition:

\(\varepsilon\) is valid, and if \(A\) and \(B\) are valid, then \(AB\) is valid; also, if \(A\) is valid, then \((A)\), \([A]\) and \(\{A\}\) are valid.

Note that any other character besides the six bracket characters is considered invalid.

inputFormat

The input consists of a single line containing a non-empty string s. This string is expected to contain only the characters ('), ')', '{', '}', '[' and ']'. If any other character is present, the string is considered invalid.

\( 1 \leq |s| \leq 2 \times 10^6 \)

outputFormat

Output a single line with True if the string is valid, and False otherwise.

()

True