Order

Interview

Time limit1sMemory limit128 MB

Summary

Recover the permutation from counts of smaller previous elements, printing IMPOSSIBLE when the counts allow no permutation.

Level: Medium5 of 10
Topics: Simulation, Math
Solved: No attempts yet

Problem

There is a sequence $S = (s_1, s_2, \dots, s_n)$ made up of $n$ distinct integers. It is a permutation that uses each integer from $1$ to $n$ exactly once, so $s_i \ne s_j$ for every $i \ne j$ and $1 \le s_i \le n$ .

From $S$ we can build a new sequence $R = (r_1, r_2, \dots, r_n)$ , where $r_i$ is the number of elements among those that come before $s_i$ , namely $\{s_1, s_2, \dots, s_{i-1}\}$ , that are smaller than $s_i$ .

For example, if $n = 10$ and $S = (6, 4, 3, 5, 1, 2, 7, 8, 9, 10)$ , then $R = (0, 0, 0, 2, 0, 1, 6, 7, 8, 9)$ .

Given a sequence $R$ , write a program that recovers the original sequence $S$ . If an $S$ corresponding to $R$ exists, it is uniquely determined, but for some inputs no such $S$ exists. For example, if $n = 5$ and $R = (0, 2, 2, 0, 1)$ , then no $S$ corresponds to this $R$ .

Input

Input is read from standard input. The first line contains the number of test cases $T$ . Each test case consists of two lines: the first line contains the length of the sequence $n$ ( $1 \le n \le 100$ ), and the second line contains the $n$ integers $r_1, r_2, \dots, r_n$ of the sequence $R$ , separated by spaces.

Output

For each test case, print the sequence $S$ corresponding to the given $R$ on one line, with its numbers separated by spaces. If $S$ cannot be recovered from $R$ , print IMPOSSIBLE on that line instead.

Examples3

Example 1

Input

3
10
0 0 0 2 0 1 6 7 6 9
10
0 0 0 0 0 0 0 0 0 0
12
0 3 4 5 0 1 2 3 4 5 6 7

Expected output

6 4 3 5 1 2 8 9 7 10
10 9 8 7 6 5 4 3 2 1
IMPOSSIBLE

Example 2
Input
```
1
5
0 1 2 3 4
```
Expected output
```
1 2 3 4 5
```
Example 3
Input
```
1
5
0 0 0 0 0
```
Expected output
```
5 4 3 2 1
```