Bạn được giao tổ chức một giải Oẳn tù tì. Giải đấu theo thể thức loại trực tiếp, kéo dài \(N\) vòng và có \(2^N\) người tham gia.

Ban đầu, các đấu thủ xếp thành hàng từ trái sang phải theo thứ tự do bạn chọn. Trong mỗi vòng, người thứ nhất đấu người thứ hai, người thứ ba đấu người thứ tư nếu có, và cứ như vậy; mọi trận diễn ra đồng thời. Người thắng ở lại hàng theo đúng thứ tự tương đối cũ, người thua rời hàng và về nhà. Sau đó vòng mới bắt đầu. Quá trình tiếp tục tới khi chỉ còn một người, và người đó là nhà vô địch.

Trong mỗi trận Oẳn tù tì, hai người bí mật chọn một trong Búa, Bao hoặc Kéo, rồi so sánh. Búa thắng Kéo, Kéo thắng Bao, Bao thắng Búa. Nếu lựa chọn của một người thắng lựa chọn của người kia, người đó thắng và trận kết thúc. Nhưng nếu hai người chọn giống nhau thì hòa; họ phải chọn lại và tiếp tục chơi cho tới khi có người thắng.

Bạn biết các đấu thủ năm nay rất bướng bỉnh và không mấy chiến thuật. Mỗi người có một lựa chọn ưa thích và chỉ dùng đúng lựa chọn ấy trong mọi trận, bất kể đối thủ làm gì. Vì vậy, nếu hai người có cùng lựa chọn gặp nhau, họ sẽ hòa mãi và trận đấu kéo dài vô tận! Nếu điều này xảy ra, giải sẽ không bao giờ kết thúc và bạn sẽ trở thành trò cười.

Năm nay có \(R\) người thích Búa, \(P\) người thích Bao và \(S\) người thích Kéo. Bạn muốn tạo một hàng đấu thủ bảo đảm giải kết thúc và có đúng một người thắng, tức không trận nào từng hòa. Sếp yêu cầu bạn lập danh sách mọi hàng hợp lệ, viết từ trái sang phải bằng R, P, S tương ứng với Búa, Bao, Kéo, rồi sắp danh sách theo thứ tự từ điển.

Bạn biết sếp sẽ lười biếng chọn ngay hàng đầu tiên trong danh sách. Hàng đó là gì? Hay bạn phải báo IMPOSSIBLE vì không thể tránh hòa?

Dữ liệu vào

Dòng đầu tiên chứa số bộ test \(T\). Mỗi dòng tiếp theo là một bộ test gồm bốn số nguyên \(N,R,P,S\) như mô tả trên.

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à IMPOSSIBLE hoặc chuỗi độ dài \(2^N\) biểu diễn hàng ban đầu nhỏ nhất theo thứ tự từ điển giải được bài toán. Mỗi ký tự phải là R, P hoặc S, và chuỗi phải chứa đúng \(R\) ký tự R, \(P\) ký tự P, \(S\) ký tự S.

Ràng buộc

• \(R+P+S=2^N\).
• \(0\le R,P,S\le2^N\).

Phân nhóm

• Test Set 1 (Hiển thị): \(1\le T\le25\), \(1\le N\le3\).
• Test Set 2 (Ẩn): \(1\le T\le75\), \(1\le N\le12\).

Đ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
1 1 1 0
1 2 0 0
2 1 1 2
2 2 0 2

Case #1: PR
Case #2: IMPOSSIBLE
Case #3: PSRS
Case #4: IMPOSSIBLE

Nguồn

Google Code Jam 2016, Vòng 2, bài Rather Perplexing Showdown.

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