TÌM KHOÁ

Phương pháp mã hoá đơn giản nhất trong mật mã học là thay thế từng ký tự của chuỗi cần mã hoá bằng một ký tự tương ứng trong bảng chữ cái theo khoá k=k₁k₂…k₂₆ là một hoán vị của 26 chữ cái thường trong bảng chữ cái tiếng Anh, trong đó k₁ được thay bằng ‘a’, k₂ được thay bằng ‘b’…

Chẳng hạn với khoá k=dbocefghijklmnapqrstuvwxyz thì chuỗi ‘cat’ được mã hoá thành ‘dot’ trong đó ‘c’ thay bằng ‘d’, ‘a’ thay bằng ‘o’ và ‘t’ thay bằng ‘t’.

Yêu cầu: cho n chuỗi ký tự s₁, s₂,…,s_n. Hãy tìm một khoá k để mã hoá s₁, s₂,…,s_n thành t₁, t₂,…,t_n sao cho t₁, t₂,…,t_n tạo thành dãy có thứ tự từ điển (t₁<= t₂<=…<=t_n)

Dữ liệu: vào từ tệp văn bản KEY.INP

+ Dòng đầu tiên chứa số nguyên dương n (1<n<=10⁵)

+ Dòng thứ i trong n dòng tiếp theo chứa chuỗi ký tự latin in thường s_i có độ dài không quá 100

Kết quả: ghi ra tệp văn bản KEY.OUT khoá k gồm 26 ký tự latin là một hoán vị của bảng chữ cái latin in thường. Nếu không tồn tại thì phải ghi thông báo ‘No Solution’.

Ví dụ:

KEY.INP	KEY.OUT
5 dog donky duck cat goose	docugnbefhijklmpqrstvwxyaz

Giải thích: Với khoá k= docugnbefhijklmpqrstvwxyaz thì các chuỗi sau phép biến đổi có thứ tự từ điển:

                  dog   ->  abe

                  donky ->   abfmhx

                  duck  ->   adcm

                  cat   ->   cyt

                  goose ->   ebbsh

SOLUTION