The peak that looks highest

You are walking along a mountain range. There is one peak every kilometre and no peaks in between. On each peak you lie down to rest, look ahead, and one of the peaks in front of you looks like the highest one. The peak that looks highest is not always the highest one. There are two reasons. A higher peak can be hidden behind a nearer and lower peak, and when you look downhill a distant peak can look higher than a close one.

To be precise, peak $B$ looks like the highest one from peak $A$ when all three of the following hold. $B$ is further along the road than $A$. Every peak between $A$ and $B$ is strictly below the line joining $A$ and $B$. Every peak past $B$ is on that line or below it.

You do not know the height of any peak, but your memory is good. You have stood on all of them and you remember which peak looked highest from each one. Invent one set of heights that agrees with that memory. You were lying down while looking, so treat every line of sight as starting at ground level on its peak.

In the picture the fourth peak looks like the highest one from the first peak and from the third peak. Lying on the second peak you cannot see the fourth peak, because the third one hides it, and the third peak looks like the highest one.

The first line contains the number of test cases $T$. Each test case takes two lines. The first line contains $N$, the number of peaks in the range. Your trip started on peak 1 and went forward to peak $N$. The second line contains $N-1$ numbers $x_1, x_2, \dots, x_{N-1}$, where $x_i$ is the index of the peak that looked highest from peak $i$. Peak $N$ is the last one, so no peak is visible ahead of it and no number is given for it.

For each test case print one line in the form Case #n: y1 y2 ... yN, where $n$ is the test case number counted from 1 and $y_i$ is the height of peak $i$. If no set of heights agrees with the memory, print Case #n: Impossible instead.

Several different sets of heights can agree with the same memory, so print only the heights that the following rule fixes.

1. For each $i$ from $1$ to $N-1$, let $r_i$ be the number of indices $j$ with $j \le i$ and $x_j = x_i$. So $r_i$ is the position of peak $i$, counted from the left, among the peaks whose highest looking peak is $x_i$.
2. Set $t_N = 0$, and for $i$ from $N-1$ down to $1$ set $t_i = t_{x_i} + r_i$.
3. Set $h_N = 0$, and for $i$ from $N-1$ down to $1$ set $h_i = h_{x_i} - t_i (x_i - i)$.
4. Let $m$ be the smallest of $h_1, h_2, \dots, h_N$ and print $y_i = h_i - m$.

Whenever any set of heights agrees with the memory, the heights this rule builds agree with it too. Every value the rule prints is an integer between $0$ and $(N-1)^2$.

• $1 \le T \le 30$
• $i < x_i \le N$
• $2 \le N \le 2000$