Bạn đang chơi Hangman với người bạn Sean. Mặc dù bạn từng nghe rằng Sean rất giỏi lấy kẹo của trẻ con, cậu ấy lại không giỏi trò chơi này. Liệu bạn có thể tận dụng chiến thuật chưa hoàn hảo của Sean để khiến cậu ấy thua đậm nhất có thể không?

Hangman được chơi như sau:

 +--+
 |  O
 | /|\       Mystery word: _ a _ a _ a _
 | / \
 |
+-+---+

• Có một từ điển \(D\) gồm tất cả các từ hợp lệ mà cả bạn và Sean đều biết. Mỗi từ chỉ gồm các ký tự a–z; đặc biệt, từ không chứa dấu cách.
• Bạn bắt đầu bằng cách chọn một từ bất kỳ trong \(D\) rồi viết nó lên bảng, thay mỗi chữ cái bằng một ô trống _.
• Trong lượt của mình, Sean có thể chọn một chữ cái và hỏi chữ đó có nằm trong từ hay không. Nếu có, bạn phải mở tất cả các vị trí chứa chữ cái ấy. Nếu không, Sean mất một điểm.
• Vòng chơi kết thúc khi tất cả các chữ cái trong từ đã được mở.
• Vòng chơi không bao giờ kết thúc sớm, bất kể Sean đã mất bao nhiêu điểm.

Sean dùng một chiến thuật rất đơn giản. Cậu lập một danh sách \(L\) chứa 26 chữ cái theo một thứ tự nào đó và lần lượt xét từng chữ cái. Nếu tồn tại ít nhất một từ trong \(D\) vừa (a) chứa chữ cái đang xét, vừa (b) phù hợp với những gì bạn đã viết trên bảng cho đến lúc đó và với kết quả của tất cả các lần đoán trước của Sean, thì Sean sẽ đoán chữ cái ấy. Nếu không, cậu bỏ qua nó. Dù trường hợp nào xảy ra, Sean cũng chuyển sang chữ cái tiếp theo trong danh sách.

Với danh sách của Sean, bạn nên chọn từ nào để khiến Sean mất nhiều điểm nhất có thể? Nếu có nhiều lựa chọn tốt như nhau, hãy chọn từ xuất hiện sớm nhất trong \(D\).

Ví dụ minh họa

Giả sử Sean quyết định đoán các chữ cái theo thứ tự bảng chữ cái, tức \(L =\) abcdefghijklmnopqrstuvwxyz, và \(D\) chứa các từ banana, caravan, pajamas. Nếu bạn chọn pajamas, ván chơi diễn ra như sau:

• Bạn bắt đầu bằng cách viết 7 ô trống _ _ _ _ _ _ _ lên bảng. Dựa vào số ô trống, Sean biết ngay từ cần đoán chỉ có thể là caravan hoặc pajamas.
• Sean bắt đầu bằng việc đoán a vì đây là chữ cái đầu tiên trong \(L\), và bạn mở tất cả vị trí của a trên bảng: _ a _ a _ a _.
• Sean bỏ qua b dù chữ này xuất hiện trong banana, vì cậu đã biết đó không phải từ của bạn.
• Sau đó cậu đoán c vì chữ này xuất hiện trong caravan. Tuy nhiên, nó không xuất hiện trong từ bạn thực sự chọn, nên Sean mất một điểm và không có chữ nào được mở thêm.
• Bằng phương pháp loại trừ, lúc này Sean biết từ của bạn buộc phải là pajamas, nên cậu lần lượt đoán j, m, p, s mà không mất thêm điểm nào.

Vì vậy, Sean mất một điểm nếu bạn chọn pajamas. Nếu chọn một trong hai từ còn lại, cậu sẽ đoán được mà không mất điểm nào.

Dữ liệu vào

Dòng đầu tiên chứa số lượng bộ test \(T\). Tiếp theo là \(T\) bộ test. Mỗi bộ test bắt đầu bằng một dòng chứa hai số nguyên \(N\) và \(M\), lần lượt là số từ trong từ điển và số danh sách cần xét.

\(N\) dòng tiếp theo chứa các từ trong từ điển, mỗi dòng một từ: \(D_1, D_2, \ldots, D_N\). Mỗi từ là một chuỗi tùy ý gồm các ký tự a–z.

\(M\) dòng cuối chứa tất cả các danh sách Sean sẽ sử dụng, mỗi dòng một danh sách: \(L_1, L_2, \ldots, L_M\). Mỗi danh sách dài đúng 26 chữ cái và chứa mỗi chữ cái đúng một lần. Sean sẽ dùng các danh sách này để đoán chữ theo cách đã mô tả ở trên.

Dữ liệu ra

Với mỗi bộ test, in một dòng có dạng Case #x: w1 w2 ... wM, trong đó \(x\) là số thứ tự bộ test (bắt đầu từ 1), và \(w_i\) là từ bạn nên chọn nếu Sean đoán các chữ cái theo thứ tự \(L_i\). Nếu nhiều từ khiến Sean mất cùng số điểm, hãy chọn từ xuất hiện sớm nhất trong từ điển.

Ràng buộc

• \(1 \le T \le 10\).
• Mỗi từ trong \(D\) có độ dài từ 1 đến 10, kể cả hai đầu mút.
• Trong cùng một bộ test, không có hai từ nào giống nhau.

Phân nhóm

• Test Set 1 (Nhìn thấy): \(1 \le N \le 100\), \(1 \le M \le 10\).
• Test Set 2 (Ẩn): \(1 \le N \le 10000\), \(1 \le M \le 100\).

Đ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ụ

2
3 2
banana
caravan
pajamas
abcdefghijklmnopqrstuvwxyz
etaoisnhrdlcumwfgypbvkjxqz
4 1
potato
tomato
garlic
pepper
zyxwvutsrqponmlkjihgfedcba

Case #1: pajamas caravan
Case #2: garlic

Nguồn

Google Code Jam 2011, Vòng 1A, bài The Killer 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.