Given a string s containing only the characters (, ), {, }, [, ], determine if the input string is valid.

An input string is valid if:

1. Open brackets are closed by the same type.
2. Open brackets are closed in the correct order.
3. Every close bracket has a corresponding open one.

Example

Input:  "()[]{}"
Output: true

Input:  "(]"
Output: false