Valid Bracket Sequence

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

• Every opening bracket has a corresponding closing bracket of the same type.
• Brackets are closed in the correct order.

Mathematically, if we denote the set of bracket types as \( \{ ( , \{ , [ \} \}, \) then the sequence \( s \) is valid if for each opening bracket there exists a matching closing bracket and the nested structure is preserved.

For example, the sequence ()[]{} is valid whereas (] is not. The empty string is also considered valid.

inputFormat

The input consists of a single line that contains a string s comprised only of the characters '(', ')', '{', '}', '[' and ']'.

outputFormat

Output a single line containing either True if the string is a valid bracket sequence or False otherwise.

()

True