Description

你正在山脉中行走。在这片山脉中，每隔一公里就有一座山峰，且中间没有其他山峰。在每一座山峰上，你都会躺下来休息，向前眺望，并会觉得前方某一座山峰是最高的。实际上，看起来最高的山峰未必真的最高，原因有两个：可能有一座更高的山峰被离你更近但较矮的山峰挡住了；或者你是在俯视，远处的山峰看起来比附近的更高。

更准确地说，当我们说从山峰 $A$ 看过去，山峰 $B$ 看起来最高，意思是：$B$ 比 $A$ 更靠前；$A$ 和 $B$ 之间的所有山峰都在连接 $A$ 和 $B$ 的直线下方；$B$ 之后的所有山峰都在该直线下方或正好在直线上。

你并不知道每座山峰的具体高度，但你记忆力极佳——你去过所有山峰，并且记得每座山峰上看起来最高的是哪一座。你希望构造一组山峰的高度，使其与这些观测信息一致。注意你是躺着看的，所以我们假设你总是从每座山峰的地面水平观测。

在这个例子中，从第一座和第三座山峰看，第四座山峰看起来最高。当你躺在第二座山峰时，看不到第四座，因为第三座挡住了视线，所以第三座看起来最高。

Input Format

输入的第一行为测试用例数 $T$。接下来有 $T$ 组测试数据，每组两行。第一行为一个整数 $N$，表示山峰数量。你从第 $1$ 座山峰出发，依次前进到第 $N$ 座。下一行有 $N-1$ 个整数 $x_i$，第 $i$ 个数表示从第 $i$ 座山峰看起来最高的是第 $x_i$ 座山峰（注意第 $N$ 座山峰是最后一座，从那里看不到别的山峰）。

Output Format

对于每个测试用例，输出一行 "Case #$n$: $y_1$ $y_2$ \dots $y_N$"，其中 $n$ 为测试用例编号（从 $1$ 开始），$y_i$ 表示第 $i$ 座山峰的高度。你可以输出任意一组与输入观测信息一致的解，但所有高度必须是 $0$ 到 $10^9$ 之间的整数。

如果不存在满足条件的解，则输出 "Case #$n$: Impossible"。

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

Hint

限制条件

• $1 \leq T \leq 30$
• $i < x_i \leq N$

测试集 1（13 分，结果可见）

• $2 \leq N \leq 10$

测试集 2（14 分，结果隐藏）

• $2 \leq N \leq 2000$

翻译由 ChatGPT-4.1 完成。