Ngày xưa, nền văn minh Fractal đã tạo ra những tác phẩm nghệ thuật gồm một hàng gạch. Họ dùng hai loại gạch: vàng (G) và chì (L).

Mỗi tác phẩm Fractal được xác định bởi hai tham số: một chuỗi gốc gồm \(K\) viên gạch và một độ phức tạp \(C\). Với một chuỗi gốc cho trước, tác phẩm ở độ phức tạp 1 chính là chuỗi gốc. Tác phẩm ở độ phức tạp \(X+1\) được tạo từ tác phẩm ở độ phức tạp \(X\) như sau:

• thay mỗi viên L bằng một bản sao của chuỗi gốc;
• thay mỗi viên G bằng \(K\) viên G.

Ví dụ, với chuỗi gốc LGL, các tác phẩm có độ phức tạp từ 1 đến 3 là:

• \(C=1\): LGL (chính là chuỗi gốc);
• \(C=2\): LGLGGGLGL;
• \(C=3\): LGLGGGLGLGGGGGGGGGLGLGGGLGL.

Hình dưới minh họa cách tạo tác phẩm độ phức tạp 2 từ tác phẩm độ phức tạp 1:

https://cdn.lqdoj.edu.vn/media/pagedown-uploads/pd_1_bf2e7cbb.png

Bạn vừa phát hiện một tác phẩm Fractal, nhưng gạch quá bẩn nên không thể biết chúng làm bằng gì. Là một nhà khảo cổ am hiểu văn hóa Fractal địa phương, bạn biết \(K\) và \(C\) nhưng không biết chuỗi gốc. Vì vàng rất thú vị, bạn muốn biết tác phẩm có ít nhất một viên G hay không. Ngân sách cho phép thuê \(S\) nghiên cứu sinh; mỗi người có thể lau một viên do bạn chọn trong số \(K^C\) viên để xem đó là G hay L.

Bạn có thể chọn trước không quá \(S\) vị trí sao cho, bất kể chuỗi gốc là gì, kết quả quan sát luôn cho phép kết luận chắc chắn tác phẩm có ít nhất một G hay không không? Nếu có, hãy cho biết cần lau những vị trí nào.

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi bộ test gồm một dòng chứa ba số nguyên \(K\), \(C\) và \(S\).

Dữ liệu ra

Với mỗi bộ test, in Case #x: y, trong đó \(x\) là số thứ tự bộ test (bắt đầu từ 1), còn \(y\) là IMPOSSIBLE nếu không tồn tại tập vị trí thỏa mãn, hoặc là danh sách từ 1 đến \(S\) số nguyên dương chỉ các vị trí đủ để trả lời câu hỏi. Các vị trí được đánh số từ 1 ở ngoài cùng bên trái đến \(K^C\) ở ngoài cùng bên phải. Có thể in theo thứ tự bất kỳ, nhưng các vị trí phải đôi một khác nhau.

Nếu có nhiều tập hợp hợp lệ, có thể in bất kỳ tập nào. Hãy nhớ rằng sau khi nộp một bộ Small và được chấp nhận, bạn không thể tải rồi nộp một đầu vào Small khác; FAQ của cuộc thi giải thích kỹ hơn. Lời nhắc này không xuất hiện ở các vòng sau.

Ràng buộc

• \(1\le T\le100\).
• \(1\le K\le100\).
• \(1\le C\le100\).
• \(K^C\le10^{18}\).

Phân nhóm

• Test Set 1 (Visible): \(S=K\).
• Test Set 2 (Hidden): \(1\le S\le K\).

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

5
2 3 2
1 1 1
2 1 1
2 1 2
3 2 3

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

Nguồn

Google Code Jam 2016, Vòng loại, bài Fractiles.

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