Valid Parentheses Sequence Checker

You are given a string S consisting only of the characters ('), ')', '{', '}', '[', and ']'. Your task is to determine if the string is a valid parentheses sequence.

A valid parentheses sequence is defined as follows:

• Every opening bracket must have a corresponding closing bracket of the same type.
• The brackets must close in the correct order.

Formally, a sequence is valid if for every opening bracket, there exists a matching closing bracket such that the substring enclosed by them is also a valid sequence. For clarity, the problem can be expressed using the following condition in LaTeX:

\(\text{For any valid sequence } S, \text{ if } S = A\,B \text{ with } A \text{ and } B \text{ both valid, then } S \text{ is valid.}\)

Examples:

• () is valid.
• ()[]{{}} is valid.
• (] is not valid.
• ([{{}}]) is valid.
• {{[()]} is not valid.

inputFormat

The input is given in a single line containing a non-empty string S composed only of the characters '(', ')', '{', '}', '[' and ']'.

outputFormat

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

## sample

()

True