Valid Parentheses

Given a string containing only '(', ')', '{', '}', '[' and ']', determine if the input string is valid. A string is valid if: 1. Open brackets must be closed by the same type of brackets. 2. Open brackets must be closed in the correct order. 3. Every close bracket has a corresponding open bracket of the same type. Example: '([{}])' → valid, '([)]' → invalid, '((()' → invalid

Input

A single line containing the bracket string.

Output

'true' if valid, 'false' otherwise.

Sample

([{}])

Expected

true