Valid Parentheses

Given a string s containing only the characters '(', ')', '{', '}', '[' and ']', determine if the input string is valid. The string is valid if open brackets are closed by the same type of brackets in the correct order.

Input Format

s = parentheses string

Output Format

return true if the string is valid, otherwise false

Constraints

Examples

s = "()[]{}"

true

s = "([)]"

false