Valid Parentheses

## 🧩 Valid Parentheses

Problem Statement:
Given a string s containing only the characters '(', ')', '{', '}', '[', and ']', determine whether the input string is valid.

A string is considered valid if:

1. Every open bracket is closed by the same type of bracket.
2. Open brackets are closed in the correct order.
3. Every closing bracket has a corresponding opening bracket before it.

---

### Example 1

Input


s = "()"


Output


true


---

### Example 2

Input


s = "()[]{}"


Output


true


---


### Constraints

* 1 ≤ s.length ≤ 10⁴
* s consists only of the characters '(', ')', '{', '}', '[', and ']'.