가장 높아 보이는 봉우리

산맥을 따라 걷고 있다. 이 산맥에는 1km마다 봉우리가 하나씩 있고 그 사이에는 봉우리가 없다. 봉우리마다 누워서 쉬며 앞을 바라보면 앞쪽 봉우리 중 하나가 가장 높아 보인다. 가장 높아 보이는 봉우리가 실제로 가장 높은 봉우리는 아니다. 이유는 두 가지다. 더 높은 봉우리가 앞에 있는 낮은 봉우리에 가려질 수 있고, 내리막을 내려다보는 경우에는 멀리 있는 봉우리가 가까운 봉우리보다 높아 보일 수 있다.

정확히 말하면 봉우리 $B$가 봉우리 $A$에서 가장 높아 보인다는 것은 다음 세 조건을 모두 만족한다는 뜻이다. $B$는 $A$보다 앞에 있다. $A$와 $B$ 사이의 모든 봉우리는 $A$와 $B$를 잇는 직선보다 엄격히 아래에 있다. $B$보다 뒤에 있는 모든 봉우리는 그 직선 위에 있거나 직선보다 아래에 있다.

각 봉우리의 높이는 모르지만 기억력은 좋다. 모든 봉우리에 올라가 봤고 각 봉우리에서 어느 봉우리가 가장 높아 보였는지 전부 기억한다. 이 기억과 맞아떨어지는 높이를 하나 만들어라. 볼 때는 누워 있었으므로 시선은 항상 그 봉우리의 지면 높이에서 출발한다고 본다.

그림에서 네 번째 봉우리는 첫 번째 봉우리와 세 번째 봉우리에서 가장 높아 보인다. 두 번째 봉우리에 누우면 네 번째 봉우리가 세 번째 봉우리에 가려져 보이지 않고, 세 번째 봉우리가 가장 높아 보인다.

첫째 줄에 테스트 케이스의 수 $T$가 주어진다. 각 테스트 케이스는 두 줄이다. 첫째 줄에 산맥에 있는 봉우리의 수 $N$이 주어진다. 여행은 봉우리 1에서 시작해 봉우리 $N$까지 앞으로만 진행했다. 둘째 줄에 $N-1$개의 수 $x_1, x_2, \dots, x_{N-1}$이 주어지고, $x_i$는 봉우리 $i$에서 가장 높아 보인 봉우리의 번호다. 봉우리 $N$은 마지막 봉우리라서 앞에 보이는 봉우리가 없고, 이 봉우리에 대한 수는 주어지지 않는다.

각 테스트 케이스마다 Case #n: y1 y2 ... yN 형식으로 한 줄씩 출력한다. $n$은 1부터 시작하는 테스트 케이스 번호이고 $y_i$는 봉우리 $i$의 높이다. 기억과 맞아떨어지는 높이가 없으면 Case #n: Impossible을 출력한다.

같은 기억과 맞아떨어지는 높이는 여러 가지일 수 있으므로 다음 규칙이 정하는 높이만 출력한다.

1. $1$ 이상 $N-1$ 이하의 각 $i$에 대해 $j \le i$이고 $x_j = x_i$인 $j$의 개수를 $r_i$라 한다. 즉 $r_i$는 가장 높아 보인 봉우리가 $x_i$인 봉우리 가운데 $i$가 왼쪽에서 몇 번째인지를 나타낸다.
2. $t_N = 0$으로 두고 $i$를 $N-1$부터 $1$까지 줄여 가며 $t_i = t_{x_i} + r_i$로 정한다.
3. $h_N = 0$으로 두고 $i$를 $N-1$부터 $1$까지 줄여 가며 $h_i = h_{x_i} - t_i (x_i - i)$로 정한다.
4. $h_1, h_2, \dots, h_N$ 중 가장 작은 값을 $m$이라 하고 $y_i = h_i - m$을 출력한다.

기억과 맞아떨어지는 높이가 하나라도 있으면 이 규칙이 만드는 높이도 반드시 그 기억과 맞아떨어진다. 이 규칙이 출력하는 값은 모두 $0$ 이상 $(N-1)^2$ 이하의 정수다.

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