Người ta định nghĩa một dãy ngoặc đúng theo đệ quy như sau:

• Xâu A là xâu rỗng là một dãy ngoặc đúng chỉ chứa dấu ( hoặc ). Còn những xâu chứa những ký tự khác "(" và ")" được gọi là xâu không hợp lệ.
  
• Đi từ trái qua phải thì số lượng dấu ( bằng số lượng dấu )
  Ví dụ:
  S = "(A()B)" là dãy "KHONG HOP LE" vì chứa chữ cái A và B
  S = "()()(())" là dãy ngoặc "DUNG"
  S = "()())" là dãy ngoặc "KHONG DUNG"
  Cho xâu \(S\). Hãy kiểm tra xâu \(S\) là dãy ngoặc "DUNG", "KHONG DUNG" hay là xâu "KHONG HOP LE"
  Đầu vào
  
• Một xâu S chứa tối đa 106 phần tử
  Kết quả
  
• Thông báo "KHONG HOP LE" nếu xâu không hợp lệ
  
• Thông báo "DUNG" nếu xâu đúng
  
• Thông báo "KHONG DUNG" nếu xâu không đúng
  

input

(A()B)

output

KHONG HOP LE

input

()()(())

output

DUNG

input

((())

output

KHONG DUNG