Valid Parentheses

In this problem, you are given a string S that consists of various characters. Your task is to determine whether the string is a valid sequence of parentheses. A valid parentheses sequence is defined by the following conditions:

• Every opening bracket must have a corresponding closing bracket of the same type.
• The brackets must be closed in the correct order.
• The only permitted characters in the string are ('), ')', '[', ']', '{', and '}'. Any other character will make the string invalid.

Mathematically, a string S is valid if and only if it can be defined recursively as follows:

$$ \text{Valid}(S) := \begin{cases} \epsilon & \text{if } S \text{ is empty},\\ (\text{Valid}(S)) & \text{or } [\text{Valid}(S)] & \text{or } \{\text{Valid}(S)\} & \text{if } S \text{ is enclosed by matching brackets},\\ \text{Valid}(S_1)\text{Valid}(S_2) & \text{if } S = S_1S_2 \text{ and both are valid.} \end{cases} $$

Your program must read the input string from the standard input and output True if the string is a valid parentheses sequence and False otherwise.

inputFormat

The input consists of a single line containing a string S which represents the sequence of characters. The string may contain only the characters: '(', ')', '[', ']', '{', '}'. Any other character makes the string invalid.

Input Format:

S

outputFormat

Output a single line with True if the input string is a valid parentheses sequence; otherwise, output False.

Output Format:

True or False

## sample

()

True