Sau nhiều đêm mất ngủ, cuối cùng bạn đã dạy xong một cánh tay robot thực hiện các động tác tay cần thiết cho trò chơi Oẳn tù tì. Giờ bạn chỉ còn phải lập trình cho nó tham gia giải đấu robot sắp tới!

Trong giải đấu này, mỗi robot sử dụng một chương trình là một chuỗi nước đi; mỗi nước phải là một trong các ký tự sau: R ("Rock", Búa), P ("Paper", Bao), hoặc S ("Scissors", Kéo). Bao thắng Búa và thua Kéo; Búa thắng Kéo và thua Bao; Kéo thắng Bao và thua Búa.

Khi hai robot đối đầu trong một trận, robot đầu tiên đánh ra một nước thắng sẽ thắng trận. Ban đầu, mỗi robot đánh nước đầu tiên trong chương trình của mình. Nếu hai nước khác nhau, một nước sẽ thắng nước còn lại, vì vậy một robot sẽ thắng trận. Nếu hai nước giống nhau, mỗi robot đánh nước tiếp theo trong chương trình của mình, rồi cứ tiếp tục như vậy.

Mỗi khi một robot đã đi đến cuối chương trình và cần nước tiếp theo, nó quay lại đầu chương trình. Chẳng hạn, nước thứ năm của một robot có chương trình RSSP sẽ là R. Nếu một trận đấu kéo dài quá một googol (\(10^{100}\)) nước, ban giám khảo sẽ tung một đồng xu cân bằng để quyết định robot thắng cuộc.

Sau khi một trận kết thúc, robot thắng sẽ được đặt lại trạng thái, nên nó không có ký ức về trận đấu đó. Trong trận tiếp theo, nó lại bắt đầu bằng nước đầu tiên trong chương trình của mình, rồi cứ tiếp tục như vậy.

Giải đấu diễn ra trong \(K\) vòng và có cấu trúc loại trực tiếp theo "nhánh đấu". Tổng cộng có \(N = 2^K\) robot, được đánh số từ \(0\) đến \(N - 1\). Ở vòng đầu tiên, robot \(0\) đấu với robot \(1\), robot \(2\) đấu với robot \(3\), và cứ thế cho đến cặp robot \(N - 2\) và \(N - 1\). Các robot thua những trận đó bị loại khỏi giải. Ở vòng thứ hai, robot thắng trận \(0\)-\(1\) đối đầu với robot thắng trận \(2\)-\(3\), và cứ tiếp tục như vậy. Khi đến vòng thứ \(K\), chỉ còn một trận duy nhất và trận đó quyết định nhà vô địch chung cuộc.

Tất cả thí sinh khác đều tự tin đến mức đã công khai chương trình robot của họ trên mạng. Tuy nhiên, các robot chưa được gán số, nên không ai biết trước mình sẽ gặp những đối thủ nào. Khi biết tất cả chương trình còn lại, liệu bạn có thể viết một chương trình chắc chắn vô địch giải đấu, bất kể các số hiệu robot được gán như thế nào không?

Dữ liệu vào

Dòng đầu tiên chứa số lượng bộ test \(T\); tiếp theo là \(T\) bộ test. Mỗi bộ test bắt đầu bằng một dòng chứa số nguyên \(A\): số đối thủ (các robot khác) trong giải. Sau đó có thêm \(A\) dòng; dòng thứ \(i\) trong số này chứa chuỗi \(C_i\) gồm các chữ cái in hoa, biểu diễn chương trình của robot đối thủ thứ \(i\).

Dữ liệu ra

Với mỗi bộ test, in một dòng có dạng Case #x: y. Nếu tồn tại một chuỗi dài từ \(1\) đến \(500\) ký tự được đảm bảo sẽ vô địch giải đấu như mô tả ở trên, thì y phải là chuỗi chữ cái in hoa biểu diễn chương trình đó. Nếu không, y phải là IMPOSSIBLE, viết bằng chữ in hoa.

Ràng buộc

• \(1 \le T \le 100\).
• Mỗi ký tự trong \(C_i\) là một trong các chữ cái in hoa R, P, hoặc S, với mọi \(i\).
• \(A = 2^K - 1\) với một số nguyên \(K \ge 1\).

Phân nhóm

Test Set 1 (Visible)

• \(1 \le A \le 7\).
• Độ dài của \(C_i\) nằm trong khoảng từ \(1\) đến \(5\) ký tự, với mọi \(i\).

Test Set 2 (Hidden)

• \(1 \le A \le 255\).
• Độ dài của \(C_i\) nằm trong khoảng từ \(1\) đến \(500\) ký tự, với mọi \(i\).

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

3
1
RS
3
R
P
S
7
RS
RS
RS
RS
RS
RS
RS

Case #1: RSRSRSP
Case #2: IMPOSSIBLE
Case #3: P

Nguồn

Google Code Jam 2019, Vòng 1C, bài Robot Programming Strategy.

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