Hôm nay trời mưa, vì vậy bạn ở trong nhà xây các tháp từ những khối chữ cái. Một khối chữ cái là khối lập phương bằng gỗ có một chữ được in trên một mặt. Phông chữ khiến các khối có hướng rõ ràng: chỉ có một mặt có thể quay xuống sàn và một mặt có thể quay lên trần.

Bạn đã xây nhiều tháp riêng biệt. Bây giờ, bạn muốn ghép tất cả thành một siêu tháp: chọn một tháp làm đáy, nhấc một tháp khác lên mà không thay đổi thứ tự các khối trong nó rồi đặt nguyên tháp ấy lên trên, tiếp tục như vậy cho đến khi dùng hết mọi tháp.

Siêu tháp còn phải thỏa điều kiện: với hai khối bất kỳ mang cùng một chữ cái, mọi khối nằm giữa chúng cũng phải mang chữ ấy. Nói cách khác, mỗi chữ cái xuất hiện trong siêu tháp phải tạo thành đúng một nhóm liên tiếp gồm một hoặc nhiều khối.

Xét ba siêu tháp minh họa dưới đây. Đây là ba ví dụ riêng biệt, không được xây từ cùng một tập tháp ban đầu. Kích thước các khối khác nhau chỉ để hình vẽ vui mắt và không phải một phần của bài toán.

Hai siêu tháp bên trái hợp lệ vì mỗi chữ xuất hiện trong một nhóm liên tiếp. Siêu tháp ngoài cùng bên phải không hợp lệ vì có một chữ B nằm giữa hai chữ C.

Với các tháp đã xây, liệu bạn có thể xếp tất cả thành một siêu tháp hợp lệ không?

Dữ liệu vào

Dòng đầu chứa số lượng bộ test \(\mathbf{T}\). Tiếp theo là \(\mathbf{T}\) bộ test, mỗi bộ được mô tả bằng hai dòng.

Dòng đầu của mỗi bộ test chứa số nguyên \(\mathbf{N}\), là số tháp hiện có. Dòng thứ hai chứa \(\mathbf{N}\) chuỗi \(\mathbf{S}_1,\mathbf{S}_2,\ldots,\mathbf{S}_\mathbf{N}\) biểu diễn các tháp. Mỗi chuỗi chỉ gồm chữ cái in hoa. Ký tự thứ \(i\) của một chuỗi là chữ trên khối thứ \(i\) tính từ đáy của tháp tương ứng.

Dữ liệu ra

Với mỗi bộ test, in một dòng theo định dạng Case #x: y, trong đó \(x\) là số thứ tự bộ test (bắt đầu từ \(1\)), còn \(y\) là chuỗi biểu diễn một siêu tháp hợp lệ như mô tả, hoặc từ IMPOSSIBLE nếu không thể xây siêu tháp hợp lệ. Lưu ý rằng bản thân chuỗi IMPOSSIBLE không bao giờ biểu diễn một siêu tháp hợp lệ, vì giữa hai chữ I có các chữ khác.

Ràng buộc

• \(1\le\mathbf{T}\le100\).
• \(1\le|\mathbf{S}_i|\le10\) với mọi \(i\).

Phân nhóm

• Test Set 1 (phán quyết hiển thị): \(2\le\mathbf{N}\le6\).
• Test Set 2 (phán quyết hiển thị): \(2\le\mathbf{N}\le100\).

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

6
5
CODE JAM MIC EEL ZZZZZ
6
CODE JAM MIC EEL ZZZZZ EEK
2
OY YO
2
HASH CODE
6
A AA BB A BA BB
2
CAT TAX

Case #1: ZZZZZJAMMICCODEEEL
Case #2: IMPOSSIBLE
Case #3: IMPOSSIBLE
Case #4: IMPOSSIBLE
Case #5: BBBBBAAAAA
Case #6: IMPOSSIBLE

Nguồn

Google Code Jam 2022, Vòng 1C, bài Letter Blocks.

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