Cho chuỗi \(s\) chỉ chứ các ký tự '(', ')', '{', '}', '[' and ']', hãy kiểm tra xem chuỗi \(s\) đó có hợp lệ hay không.

Một chuỗi đầu vào hợp lệ nếu:

• Dấu ngoặc mở phải được đóng bằng dấu ngoặc cùng loại.
• Dấu ngoặc mở phải được đóng theo đúng thứ tự.
• Mỗi dấu ngoặc đóng có một dấu ngoặc mở tương ứng cùng loại.

Input

• chuỗi \(s\)

Output

• Nếu \(s\) hợp lệ thì ghi \(true\) ngược lại ghi \(false\)

Constraints

• \(1 \le s.length \le 10^4\)
• s chỉ chứa '()[]{}'.

Example

Sample input 1

()

Sample output 1

true

Sample input 2

()[]{}

Sample output 2

true

Sample input 3

(]

Sample output 3

false