Valid Parentheses

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

A string is considered valid if:

• Open brackets must be closed by the same type of brackets.
• Open brackets must be closed in the correct order.

Formally, the problem asks you to verify if the string s satisfies the following property using a stack-based approach with an expected time complexity of \(O(n)\), where \(n\) is the length of the string.

For example:

• s = "()" is valid.
• s = "()[]{}" is valid.
• s = "(]" is invalid.
• s = "([)]" is invalid.
• s = "{[]}" is valid.

inputFormat

The input consists of a single line containing the string s.

Note: The string consists solely of the characters '(', ')', '{', '}', '[' and ']'.

outputFormat

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

## sample

()

True