Valid Bracket Sequence

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

A valid bracket sequence satisfies the following conditions:

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

In other words, a string s is valid if it can be fully reduced by repeatedly removing pairs of adjacent matching brackets.

For example, the string \( (){}[] \) is valid, while \( ({[)]} \) is not.

inputFormat

A single line containing the string s which consists only of the characters '(', ')', '{', '}', '[' and ']'. The string can be empty.

outputFormat

Output a single line with either 'True' if the bracket sequence is valid, or 'False' otherwise.## sample

(){}[]

True