Kiểm tra ngoặc đúng

Submit solution
Points: 2 (partial)
Time limit: 1.0s
Memory limit: 488M
Author:
sguenm
Problem type
Allowed languages
Ada, Assembly, Awk, C, C++, C11, CLANG, CLANGX, Classical, COBOL, Coffee, CSC, D lang, DART, F95, FORTH, Fortrn, GAS32, GO, Haskell, Itercal, Java, kotlin, LEAN, LISP, LUA, MONOVB, Nasm, OCAML, Pascal, Perl, php, PIKE, prolog, Pypy, Python, Ruby 2, RUST, Scala, SCM, SED, SWIFT, TCL, TUR, V8JS, VB, ZIG

Sylv học toán khá yếu, cậu ta còn không phân biệt được các dấu ngoặc trong phép toán đã đúng logic chưa. Với chục năm học toán của mình, bạn hãy giúp Sylv kiểm tra xem chuỗi ngoặc có đúng logic không nhé.

Với một chuỗi ngoặc bao gồm các kí tự có trong "{} [] ()", chuỗi ngoặc thường được đảm bảo ko có ngoặc nhọn nào bên trong ngoặc vuông/tròn, và không có ngoặc vuông nào nằm trong ngoặc tròn. Các dấu mở ngoặc và đóng ngoặc theo đúng trật tự.

Input:

  • Dòng đầu tiên là số nguyên \(t (t \le 10)\) ứng với số bộ test.
  • t dòng tiếp theo, mỗi dòng là 1 xâu kí tự chỉ chứa các dấu ngoặc.

Output:

  • Với mỗi test, in ra \(Dung\) nếu xâu kí tự thỏa mãn đúng logic yêu cầu đề bài, in \(Sai\) với trường hợp ngược lại.

Example

Input 1

2
()()
(()

Output 1

Dung
Sai

Input 2

2
([]())
{[()]}

Output 2

Sai
Dung

Comments