Mousetrap là một trò chơi bài đơn giản dành cho một người chơi. Trò chơi được chơi với một bộ bài đã được xáo trộn gồm các lá bài được đánh số từ \(1\) đến \(K\), úp xuống.

Bạn chơi bằng cách lật lá bài trên cùng của bộ bài và sau đó đặt nó xuống dưới cùng của bộ bài, đồng thời đếm xem bạn đã lật được bao nhiêu lá bài. Nếu bạn lật được một lá bài có số khớp với số lần đếm hiện tại, hãy loại bỏ nó khỏi bộ bài và thiết lập lại (reset) số lần đếm. Nếu số lần đếm đạt đến \(K+1\), bạn đã thua. Nếu bộ bài hết bài, bạn thắng.

Giả sử bạn có một bộ bài gồm 5 lá, theo thứ tự 2, 5, 3, 1, 4.
Bạn sẽ lật lá 2 ở lần đếm 1, lá 5 ở lần đếm 2, sau đó là lá 3 ở lần đếm 3. Vì giá trị khớp với số lần đếm, bạn loại bỏ lá 3 khỏi bộ bài và reset số lần đếm. Bây giờ bạn còn 4 lá bài theo thứ tự 1, 4, 2, 5. Tiếp theo bạn lật lá 1 ở lần đếm 1, và cũng loại bỏ nó (bạn đang làm rất tốt!). Tiếp tục theo cách này, bạn sẽ lần lượt loại bỏ lá 2, sau đó là lá 4, và cuối cùng là lá 5 để giành chiến thắng.

Bạn muốn sắp xếp một bộ bài sao cho bạn sẽ thắng trò chơi và loại bỏ các lá bài theo thứ tự tăng dần. Chúng ta sẽ gọi một bộ bài được sắp xếp theo cách này là "hoàn hảo".
Ví dụ, với 4 lá bài, bạn có thể sắp xếp bộ bài là 1, 4, 2, 3, và bạn sẽ thắng bằng cách loại bỏ các lá bài theo thứ tự 1, 2, 3, 4.

Dữ liệu vào

Dòng đầu tiên của dữ liệu vào cho biết số lượng bộ test, \(T\).
Mỗi bộ test bắt đầu bằng một dòng chứa \(K\), số lượng lá bài trong bộ bài.
Dòng tiếp theo bắt đầu bằng một số nguyên \(n\), theo sau là \(n\) số nguyên (\(d_1, d_2, \dots\)), là các chỉ số trong bộ bài.

Dữ liệu ra

Đối với mỗi bộ test, hãy xuất một dòng chứa "Case #\(x\): " theo sau là \(n\) số nguyên (\(k_1, k_2, \dots\)), trong đó \(k_i\) là giá trị của lá bài tại chỉ số \(d_i\) của một bộ bài hoàn hảo có kích thước \(K\).
Các số trong đầu ra phải được phân tách bằng dấu cách và phải có ít nhất một dấu cách sau dấu hai chấm trong mỗi dòng "Case #\(x\):".

Ràng buộc

Phân nhóm

• Small dataset (Test set 1 - Visible):

• \(T = 100\).

• \(1 \le K \le 5000\).
• \(1 \le n \le 100\).
• \(1 \le d_i \le K\).

• Large dataset (Test set 2 - Hidden):

• \(T = 10\).

• \(1 \le K \le 1000000\).
• \(1 \le n \le 100\).
• \(1 \le d_i \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ụ

2
5
5 1 2 3 4 5
15
4 3 4 7 10

Case #1: 1 3 2 5 4
Case #2: 2 8 13 4

Nguồn

Google Code Jam 2008, Vòng 1B, bài Mousetrap.

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