Valid Parentheses

You are given a string s that contains only these characters: (, ), {, }, [, ].

Your task is to check whether the string is valid.

A string is valid if:

1. Every opening bracket has a matching closing bracket of the same type.

2. Brackets are closed in the correct order.

3. A closing bracket must not appear before its corresponding opening bracket.

Example 1

Input

s = "()"

Output

true

Constraints

• 1 ≤ s.length ≤ 10⁴

• s contains only: (, ), {, }, [, ]