Ở lớp học nọ có $2^n$ học sinh được đánh số từ $0$ đến $2^n - 1$. Có $n$ câu lạc bộ được tổ chức trong lớp học, được đánh số từ $0$ đến $n - 1$. Học sinh $i$ thuộc câu lạc bộ thứ $j$ khi và chỉ khi bit thứ $j$ được bật trong biểu diễn nhị phân của $i$. Ví dụ, khi $n = 4$, thì các học sinh thuộc câu lạc bộ thứ $2$ là $4, 5, 6, 7, 12, 13, 14, 15$.
Cuối tuần này sẽ có lễ hội chơi oẳn tù tì, và các câu lạc bộ muốn tổ chức các giải đấu với nhau! Với một tập hợp các câu lạc bộ $S$ ($S$ không rỗng), một giải đấu diễn ra như sau:
- Đầu tiên, tất cả các học sinh không nằm trong bất kì câu lạc bộ nào không thuộc $S$ đứng thành một hàng ngang, thứ tự tăng dần từ trái qua phải. Ví dụ, khi $n = 4$, $S = {1, 3}$, thì các học sinh $0$, $2$, $8$, $10$ sẽ đứng thành hàng ngang theo thứ tự như trên.
- Thực hiện liên tục các hành động sau khi hàng ngang còn có ít nhất hai học sinh:
- Người thứ nhất và người thứ hai sẽ chơi với nhau một ván oẳn tù tì. Cụ thể hơn:
- Nếu hai người ra khác nhau thì người ra bao thắng người ra búa, người ra búa thắng người ra kéo, người ra kéo thắng người ra bao.
- Nếu hai người ra giống nhau thì người thứ hai thắng.
- Người thua cuộc sẽ rời khỏi hàng ngang.
- Người thứ nhất và người thứ hai sẽ chơi với nhau một ván oẳn tù tì. Cụ thể hơn:
- Người cuối cùng còn ở trong hàng ngang là người chiến thắng.
Bách và Minh đang cá với nhau về kết quả của từng giải đầu một. Qua điều tra, Bách biết được rằng học sinh thứ $i$ sẽ chỉ chơi duy nhất một loại $a_i \in {R, P, S}$, với $R$ tương ứng với búa, $P$ tương ứng với bao, $S$ tương ứng với kéo. Hãy giúp Bách tìm xem với mỗi giải đấu, người chiến thắng chơi như thế nào.
Dữ liệu vào
Dòng đầu tiên nhập vào số nguyên dương ~n~ (~1 \le n \le 20~).
Dòng thứ hai nhập vào ~2^n~ kí tự ~a_0, a_1, \dots, a_{2^n - 1}~ (~a_i \in \{R, P, S\}~ ~\forall~ ~0 \le i < 2^n~).
Kết quả ra
Với mỗi ~s~ từ ~1~ đến ~2^n - 1~:
- Gọi ~S~ là tập hợp các câu lạc bộ có bit tương ứng trong biểu diễn nhị phân của ~s~ bật. Ví dụ, với ~n = 4~ và ~s = 10~, thì ~S = \{1, 3\}~.
- In ra kí tự tương ứng với cách chơi của người chiến thắng giải đấu tương ứng với ~S~, với quy ước tương tự như bên trên: ~R~ tương ứng với búa, ~P~ tương ứng với bao, ~S~ tương ứng với kéo.
Lưu ý: Các kí tự được in ra trên cùng một dòng!
Ràng buộc
- Có ~15\%~ số test ứng với ~1 \le n \le 14~.
- Có ~25\%~ số test ứng với ~1 \le n \le 17~.
- Còn lại ~60\%~ số test không có ràng buộc gì thêm.
Ví dụ 1
Dữ liệu
2
RSPS
Kết quả
RPS
Giải thích
- Khi ~s = 1~, các cách chơi của những người đứng trong hàng ngang là ~RS~. Học sinh có số thứ tự ~0~ thắng, nên ta in ra ~R~.
- Khi ~s = 2~, các cách chơi của những người đứng trong hàng ngang là ~RP~. Học sinh có số thứ tự ~2~ thắng, nên ta in ra ~P~.
- Khi ~s = 3~, các cách chơi của những người đứng trong hàng ngang là ~RSPS~. Học sinh có số thứ tự ~3~ thắng, nên ta in ra ~S~.
Ví dụ 2
Dữ liệu
4
RSPPSSPRRSPSRRRS
Kết quả
RPPRRSRRRPSRRPR
Bình luận