Trình soạn thảo mã nguồn mà nhóm của Minh viết cho bài tập lớn môn Kỹ thuật lập trình cần cảnh báo khi các dấu ngoặc bị đóng mở sai. Để kiểm tra, nó lược bỏ mọi ký tự khác, chỉ giữ lại các dấu ngoặc tròn ( ), ngoặc vuông [ ] và ngoặc nhọn { }.

Một xâu được gọi là dãy ngoặc đúng nếu nó được tạo thành theo các quy tắc sau:

• xâu rỗng là dãy ngoặc đúng;
• nếu ~A~ là dãy ngoặc đúng thì (~A~), [~A~] và {~A~} cũng là dãy ngoặc đúng;
• nếu ~A~ và ~B~ là dãy ngoặc đúng thì xâu ~AB~ (viết ~B~ liền sau ~A~) cũng là dãy ngoặc đúng.

Ba loại ngoặc bình đẳng với nhau: loại nào cũng có thể nằm trong loại nào.

Yêu cầu

Cho ~T~ xâu, với mỗi xâu hãy cho biết nó có phải là dãy ngoặc đúng hay không.

Dữ liệu vào

• Dòng thứ nhất chứa số nguyên ~T~;
• ~T~ dòng tiếp theo, mỗi dòng chứa một xâu khác rỗng chỉ gồm các ký tự ( ) [ ] { } viết liền nhau.

Kết quả ra

Ghi ra ~T~ dòng, dòng thứ ~i~ ghi YES nếu xâu thứ ~i~ là dãy ngoặc đúng, ngược lại ghi NO.

Ràng buộc

~1 \le T \le 1000~; tổng độ dài của ~T~ xâu không vượt quá ~10^6~.

• Subtask 1 (30% số điểm – test 01–06): chỉ có hai loại ký tự ( và );
• Subtask 2 (30% số điểm – test 07–12): tổng độ dài các xâu không quá ~5000~;
• Subtask 3 (40% số điểm – test 13–20): không có ràng buộc bổ sung.

Ví dụ

Dữ liệu vào mẫu 1

6
()[]{}
([{}])
([)]
((
)(
{[]}()

Kết quả ra mẫu 1

YES
YES
NO
NO
NO
YES

Giải thích

Xâu thứ ba sai vì hai cặp ngoặc "cài răng lược" (ngoặc vuông chưa đóng thì đã gặp ngoặc tròn đóng); xâu thứ tư thừa hai ngoặc mở; xâu thứ năm có ngoặc đóng đứng trước ngoặc mở dù số lượng bằng nhau.