Vincent và Desta là bạn từ thuở nhỏ. Hôm nay, Vincent dùng các miếng chữ để cho Desta xem \(N\) từ phân biệt, mỗi từ dài \(L\) ký tự. Mỗi miếng mang một chữ cái tiếng Anh in hoa và một số từ 1 đến \(L\). Một từ được tạo bởi \(L\) miếng có số từ 1 đến \(L\) theo đúng thứ tự. Các từ của Vincent không nhất thiết là từ tiếng Anh có nghĩa.

Ví dụ, nếu \(N=3\), \(L=4\) và các từ là {CAKE, TORN, SHOW}, Vincent phải cho Desta xem các miếng sau:

C₁ A₂ K₃ E₄
T₁ O₂ R₃ N₄
S₁ H₂ O₃ W₄

Desta cho rằng tạo từ rất dễ và muốn tạo một từ mới tuân thủ quy tắc trên nhưng không trùng bất kỳ từ nào của Vincent. Desta không có miếng chữ riêng, nên phải dùng các miếng của Vincent.

Với ví dụ trên, Desta có thể tạo CORN, SAKE hoặc CHRE (từ của Desta cũng không cần có nghĩa):

C₁ O₂ R₃ N₄
S₁ A₂ K₃ E₄
C₁ H₂ R₃ E₄

Ba dòng trên độc lập; Desta chỉ cần tạo một từ mới. Tuy nhiên, cậu không thể tạo WAKE vì không có miếng chữ W mang số 1, và cũng không thể tạo COO vì từ đó sai độ dài.

Đôi khi không thể tạo từ mới. Nếu Vincent chỉ có một từ thì Desta không thể tạo gì khác. Hoặc nếu Vincent có {AA, AB, BA, BB}, mọi từ Desta ghép được đều đã có sẵn.

Hãy giúp Desta chọn một từ có thể ghép chỉ từ những miếng Vincent đã dùng, hoặc cho biết điều đó là bất khả thi.

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\).

Mỗi bộ test bắt đầu bằng hai số nguyên \(N,L\): số từ của Vincent và độ dài mỗi từ. Tiếp theo là \(N\) dòng; dòng thứ \(i\) chứa một chuỗi gồm \(L\) chữ cái tiếng Anh in hoa biểu diễn từ thứ \(i\).

Dữ liệu ra

Với mỗi bộ test, in Case #x: y, trong đó \(x\) là số thứ tự bộ test, bắt đầu từ 1, và \(y\) là một từ hợp lệ Desta có thể chọn, hoặc - (một dấu gạch ngang duy nhất, mã ASCII 45) nếu không tồn tại từ hợp lệ. Nếu có nhiều đáp án, có thể in bất kỳ đáp án nào.

Ràng buộc

• \(1\le T\le100\).
• Không có hai từ đầu vào nào giống nhau.

Phân nhóm

• Test Set 1 (Hiển thị): \(1\le N\le26^2\); \(1\le L\le2\).
• Test Set 2 (Ẩn): \(1\le N\le2000\); \(1\le L\le10\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

5
4 1
A
B
C
D
4 2
WW
AA
SS
DD
4 2
AA
AB
BA
BB
3 4
CAKE
TORN
SHOW
5 7
HELPIAM
TRAPPED
INSIDEA
CODEJAM
FACTORY

Case #1: -
Case #2: WA
Case #3: -
Case #4: CORN
Case #5: HOLIDAY

Nguồn

Google Code Jam 2018, Vòng 1C, bài A Whole New Word.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.