Trong trò chơi truyền hình The Last Word, người dẫn bắt đầu một lượt bằng cách cho thí sinh xem chuỗi \(S\) gồm các chữ cái tiếng Anh in hoa. Thí sinh có một bảng trắng ban đầu trống. Người dẫn lần lượt đưa các chữ của \(S\) theo đúng thứ tự. Với chữ đầu tiên, thí sinh viết nó lên bảng; đây được tính là từ đầu tiên dù chỉ dài một chữ. Sau đó, với mỗi chữ mới, thí sinh phải viết nó vào đầu hoặc cuối từ hiện có trước khi nhận chữ tiếp theo (hoặc kết thúc trò chơi).

Ví dụ \(S=\) CAB. Sau khi viết C, có bốn chuỗi lựa chọn:

• đặt A trước C thành AC, rồi B trước AC thành BAC;
• đặt A trước C thành AC, rồi B sau AC thành ACB;
• đặt A sau C thành CA, rồi B trước CA thành BCA;
• đặt A sau C thành CA, rồi B sau CA thành CAB.

Từ sau khi dùng hết các chữ của \(S\) được gọi là last word. Thí sinh thắng nếu từ của mình đứng cuối theo thứ tự bảng chữ cái trong tất cả các last word có thể tạo. Với ví dụ trên, từ thắng là CAB, tình cờ giống chuỗi gốc. Với \(S=\) JAM, từ thắng là MJA.

Bạn là thí sinh tiếp theo và vừa được xem \(S\). Hãy tạo last word chiến thắng.

Dữ liệu vào

Dòng đầu chứa \(T\). Mỗi bộ test gồm một dòng chứa chuỗi \(S\).

Dữ liệu ra

Với mỗi bộ test, in Case #x: y, trong đó \(x\) bắt đầu từ 1 và \(y\) là last word chiến thắng.

Ràng buộc

• \(1\le T\le100\).

Phân nhóm

• Test Set 1 (Visible): \(1\le |S|\le15\).
• Test Set 2 (Hidden): \(1\le |S|\le1000\).

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

7
CAB
JAM
CODE
ABAAB
CABCBBABC
ABCABCABC
ZXCASDQWE

Case #1: CAB
Case #2: MJA
Case #3: OCDE
Case #4: BBAAA
Case #5: CCCABBBAB
Case #6: CCCBAABAB
Case #7: ZXCASDQWE

Nguồn

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