Một đám cháy nhỏ bùng lên trong phòng thượng viện, và mọi người cần được sơ tán!

Trong phòng có một số thượng nghị sĩ, mỗi người thuộc một trong \(N\) đảng chính trị. Các đảng được đặt tên theo \(N\) chữ cái tiếng Anh viết hoa đầu tiên.

Cửa thoát hiểm đủ rộng cho tối đa hai thượng nghị sĩ, nên ở mỗi bước sơ tán, bạn có thể đưa một hoặc hai người ra khỏi phòng.

Quy tắc thượng viện cho phép những người còn trong phòng biểu quyết bất kỳ dự luật nào vào bất kỳ lúc nào, kể cả giữa quá trình sơ tán! Vì vậy, phải sơ tán sao cho không đảng nào từng có đa số tuyệt đối. Nói cách khác, sau bất kỳ bước sơ tán nào, không được có quá một nửa số thượng nghị sĩ còn trong phòng thuộc cùng một đảng.

Bạn có thể lập một kế hoạch sơ tán không? Thượng viện đang trông cậy vào bạn!

Dữ liệu vào

Dòng đầu tiên chứa số bộ test \(T\). Mỗi bộ test gồm hai dòng. Dòng đầu chứa số nguyên \(N\), là số đảng. Dòng thứ hai chứa \(N\) số nguyên \(P_1,P_2,\ldots,P_N\), trong đó \(P_i\) là số thượng nghị sĩ của đảng mang tên chữ cái thứ \(i\) trong bảng chữ cái.

Dữ liệu ra

Với mỗi bộ test, in một dòng Case #x: y, trong đó x là số thứ tự bộ test (bắt đầu từ 1), còn y là kế hoạch sơ tán. Kế hoạch là danh sách các chỉ dẫn cách nhau bằng dấu cách, theo đúng thứ tự thực hiện. Mỗi chỉ dẫn gồm một hoặc hai ký tự, biểu diễn đảng của những thượng nghị sĩ được đưa ra ở bước đó.

Đề bài bảo đảm luôn tồn tại ít nhất một kế hoạch hợp lệ. Nếu có nhiều kế hoạch, bạn có thể in bất kỳ kế hoạch nào.

Ràng buộc

• \(1 \le T \le 50\).
• Trước khi sơ tán, không đảng nào có đa số tuyệt đối.
• \(1 \le P_i \le 1000\) với mọi \(i\).

Phân nhóm

• Test Set 1 (Hiển thị): \(2 \le N \le 3\) và \(\sum P_i \le 9\).
• Test Set 2 (Ẩn): \(2 \le N \le 26\) và \(\sum P_i \le 1000\).

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

4
2
2 2
3
3 2 2
3
1 1 2
3
2 3 1

Case #1: AB BA
Case #2: AA BC C BA
Case #3: C C AB
Case #4: BA BB CA

Nguồn

Google Code Jam 2016, Vòng 1C, bài Senate Evacuation.

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