Bạn đang đi bộ qua một dãy núi. Trong dãy núi này, cứ mỗi km lại có một đỉnh núi và không có đỉnh nào ở giữa. Tại mỗi đỉnh núi, bạn nằm xuống nghỉ ngơi, nhìn về phía trước và thấy một trong những đỉnh phía trước là đỉnh cao nhất. Đỉnh có vẻ cao nhất đó có thể không thực sự là đỉnh cao nhất vì hai lý do: có thể có một đỉnh cao hơn bị che khuất bởi một đỉnh khác gần bạn hơn và thấp hơn; hoặc bạn có thể đang nhìn xuống, và một đỉnh ở xa có thể trông cao hơn một đỉnh ở gần.

Chính xác hơn, khi chúng ta nói rằng đỉnh \(B\) trông có vẻ cao nhất từ đỉnh \(A\), điều đó có nghĩa là:

• \(B\) nằm xa hơn \(A\) trên đường đi.
• Tất cả các đỉnh nằm giữa \(A\) và \(B\) đều nằm dưới đường thẳng nối hai đỉnh \(A\) và \(B\).
• Tất cả các đỉnh xa hơn \(B\) đều nằm dưới hoặc nằm trên đường thẳng này.

Bạn không biết chiều cao của mỗi đỉnh, nhưng bạn có trí nhớ rất tốt; bạn đã đi qua tất cả các đỉnh và nhớ được đỉnh nào trông có vẻ cao nhất từ mỗi đỉnh đó. Bạn muốn tìm một bộ chiều cao cho các đỉnh sao cho phù hợp với thông tin đó. Lưu ý rằng bạn đã nằm xuống khi nhìn, vì vậy chúng ta giả định bạn luôn nhìn từ mức mặt đất trên mỗi đỉnh.

Trong ví dụ này, đỉnh thứ tư trông có vẻ cao nhất từ đỉnh thứ nhất và thứ ba. Khi bạn nằm trên đỉnh thứ hai, bạn không thể nhìn thấy đỉnh thứ tư; đỉnh thứ ba đã che khuất nó và trông có vẻ cao nhất.

Dữ liệu vào

Dòng đầu tiên của đầu vào cho biết số lượng bộ thử nghiệm, \(T\). \(T\) bộ thử nghiệm tiếp theo, mỗi bộ gồm hai dòng:

• Dòng đầu tiên chứa một số \(N\), số lượng đỉnh núi. Bạn bắt đầu chuyến đi tại đỉnh \(1\) và đi tiếp đến đỉnh \(N\).
• Dòng tiếp theo chứa \(N-1\) số \(x_i\). Số thứ \(i\) biểu thị chỉ số của đỉnh trông có vẻ cao nhất từ đỉnh \(i\) (lưu ý rằng đỉnh \(N\) là đỉnh cuối cùng, nên không có đỉnh nào khác để nhìn từ đó).

Dữ liệu ra

Với mỗi bộ thử nghiệm, xuất một dòng chứa "Case #n: \(y_1\) \(y_2\) ... \(y_N\)", trong đó \(n\) là số thứ tự bộ thử nghiệm (bắt đầu từ 1) và \(y_i\) là chiều cao của đỉnh thứ \(i\). Bạn có thể xuất bất kỳ giải pháp nào phù hợp với dữ liệu đầu vào, miễn là tất cả các chiều cao bạn xuất ra phải là số nguyên từ \(0\) đến \(10^9\), bao gồm cả hai đầu mút.

Nếu không có giải pháp nào khả thi, hãy xuất "Case #n: Impossible".

Ràng buộc

• \(1 \le T \le 30\).
• \(i < x_i \le N\).

Phân nhóm

• Test set 1 (Visible): \(2 \le N \le 10\).
• Test set 2 (Hidden): \(2 \le N \le 2000\).

Đ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
6
2 3 4 5 6
4
4 4 4
4
3 4 4
4
4 3 4

Case #1: 10 10 10 10 10 2
Case #2: 10 20 40 80
Case #3: Impossible
Case #4: 5 3 6 8

Nguồn

Google Code Jam 2012, Vòng 2, bài Mountain View.

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