Các thành viên ban giám khảo của một cuộc thi ICPC khu vực đã không thể đảm bảo các điều kiện phù hợp cho cuộc thi, vì vậy họ quyết định xếp hạng các đội theo thứ tự từ điển. Do đó, đội có tên theo thứ tự từ điển nhỏ nhất sẽ được tuyên bố là đội chiến thắng.
Nhân vật chính của bài toán này, Etna, là đội trưởng của một đội mà chúng ta sẽ giấu tên, nhưng chỉ cần biết rằng tên đội bắt đầu bằng chữ cái ‘Z’, điều này khiến đội ở một vị trí khá bất lợi. Sau những cuộc thảo luận kéo dài với ban giám khảo, Etna đã giành được một cách xếp hạng công bằng hơn. Thật không may, các đội vẫn sẽ được xếp hạng theo thứ tự từ điển, nhưng định nghĩa về thứ tự từ điển sẽ thay đổi. Cụ thể hơn, ban giám khảo sẽ chọn ngẫu nhiên một hoán vị của các chữ cái trong bảng chữ cái tiếng Anh và thứ tự từ điển sẽ được xác định một cách tự nhiên dựa trên hoán vị đó. Nói cách khác, thứ tự của các chữ cái trong hoán vị sẽ tương ứng với thứ tự từ điển của chúng.
Etna ngay lập tức lấy máy tính xách tay của mình ra và viết một chương trình tìm kiếm một hoán vị các chữ cái sao cho chính đội của cô ấy sẽ giành chiến thắng trong cuộc thi. Thật không may, chương trình vẫn chưa chạy xong cho đến tận ngày nay. Hãy giúp Etna và viết một chương trình hiệu quả hơn với cùng chức năng đó.
Dữ liệu vào
Dòng đầu tiên chứa số nguyên dương $N$, đại diện cho số lượng đội tham gia cuộc thi.
Trong $N$ dòng tiếp theo là tên của các đội tham gia cuộc thi. Tên của mỗi đội bao gồm một từ được tạo thành từ các chữ cái thường trong bảng chữ cái tiếng Anh. Tất nhiên, tên của các đội là khác nhau.
Dữ liệu ra
Đối với mỗi đội, theo thứ tự được liệt kê trong dữ liệu đầu vào, cần in ra trên một dòng riêng biệt hoán vị các chữ cái tiếng Anh mà theo đó đội đó sẽ giành chiến thắng trong cuộc thi. Nếu không tồn tại hoán vị nào như vậy, cần in ra từ “nemoguce”, và nếu có nhiều hoán vị như vậy, chỉ cần in ra bất kỳ hoán vị nào.
Nhiệm vụ con
Gọi $L$ là tổng độ dài các từ của tất cả $N$ đội, và $K$ là số lượng chữ cái khác nhau xuất hiện trong tên của tất cả các đội.
| Nhiệm vụ con | Số điểm | Giới hạn |
|---|---|---|
| 1 | 13 | $1 \le N \le 100, 1 \le L \le 10\,000, 1 \le K \le 6$ |
| 2 | 32 | $1 \le N \le 350, 1 \le L \le 10\,000, 1 \le K \le 26$ |
| 3 | 55 | $1 \le N \le 25\,000, 1 \le L \le 1\,000\,000, 1 \le K \le 26$ |
Ví dụ
Dữ liệu vào 1
3 war zag wro
Dữ liệu ra 1
agorwzbcdefhijklmnpqstuvxy agorzwbcdefhijklmnpqstuvxy gorawzbcdefhijklmnpqstuvxy
Dữ liệu vào 2
3 b ab aa
Dữ liệu ra 2
bacdefghijklmnopqrstuvwxyz nemoguce abcdefghijklmnopqrstuvwxyz
Dữ liệu vào 3
7 bcada dbaab bbabc ababb aacdf bcdff baddb
Dữ liệu ra 3
cbadfeghijklmnopqrstuvwxyz cdabfeghijklmnopqrstuvwxyz bacdfeghijklmnopqrstuvwxyz nemoguce abcdfeghijklmnopqrstuvwxyz cbdafeghijklmnopqrstuvwxyz nemoguce