Valid Parentheses

Easy

Given a string containing only ()[]{} brackets, determine whether the string is valid. A valid string must close every opening bracket in the correct order.

Input Format

Single line containing string s

Output Format

Print true or false (lowercase).

Constraints

1 <= s.length <= 20000
s consists only of characters: ()[]{}

Examples

Input

()[]{}

Output

true

Explanation

All bracket types are closed in valid order.

Input

([)]

Output

false

Explanation

The nesting order is invalid.

Hints

Hint 1

Hint 2

Code

Upload

Input

Expected Output

true

All bracket types are closed in valid order.

Run uses the currently selected testcase. Submit always evaluates your code against the full hidden test suite from the database.