Cho một dãy gồm các ký tự ngoặc (, ), [, ], {, }. Dãy được gọi là hợp lệ nếu mỗi ngoặc mở có một ngoặc đóng cùng loại tương ứng và các cặp ngoặc lồng nhau đúng thứ tự (ví dụ ([]{}) hợp lệ, ([)] không hợp lệ). Hãy kiểm tra tính hợp lệ. Gợi ý: dùng stack.

Dữ liệu vào

Một dòng chứa dãy ngoặc có độ dài không quá ~10^5~ (có thể là dòng rỗng).

Kết quả

In ra YES nếu dãy hợp lệ, ngược lại in NO.

Ví dụ

Ví dụ 1

Input:

([]{})

Output:

YES

Ví dụ 2

Input:

([)]

Output:

NO

Giải thích

Gặp ngoặc mở thì đẩy vào ngăn xếp; gặp ngoặc đóng thì phải khớp với ngoặc mở ở đỉnh ngăn xếp. Cuối cùng ngăn xếp phải rỗng.