Problem1273-- Available Insertion Sequences

1273: Available Insertion Sequences

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 0  Solved: 0
[Submit] [Status] [Web Board] [Creator:]

Description

Bob has just learned hash in today's lesson. A hash function is any function that can be used to map data of arbitrary size to data of fixed size. As a beginner, Bob simply chooses a hash table of size n with hash function h(x) = x % n.

Unfortunately, the hash function may map two distinct value to the same hash value. For example, when n = 9 we have h(7) = h(16) = 7. It will cause a failure in the procession of insertion. In this case, Bob will check whether the next position (h(x) + 1) % n is available or not. This task will not be finished until an available position is found. If we insert {7, 8, 16} into a hash table of size 9, we will finally get {16, -1, -1, -1, -1, -1, -1, 7, 8}. Available positions are labeled as -1.

After done all the exercises, Bob became curious to the inverse problem. Can we rebuild the insertion sequence from a hash table? If there are multiple available insertion sequences, Bob will just select the smallest one under lexicographical order.

{a1, a2, .., an} is lexicographically smaller than {b1, b2, .., bn} if and only if there exists i (1 ≤ i ≤ n) satisfy that ai < bi and aj = bj (1 ≤ j < i).

Input

There are multiple cases.
The first line of input is an integer T (1 ≤ T ≤ 20) which indicates the cases of test data.
The first line of each case contains a positive integer n (1 ≤ n ≤ 105). The second line contains exactly n numbers ai (-1 ≤ ai ≤ 108).
It is guaranteed for each test cases that at least one available insertion sequences exist.

Output

For each case, please output smallest available insertion sequence in a single line. Print an empty line when the available insertion sequence is empty.

Sample Input Copy

4 
9 
16 -1 -1 -1 -1 -1 -1 7 8 
4 
8 5 2 3 
4 
-1 -1 -1 -1 
10 
8 10 -1 -1 34 75 86 55 88 18 

Sample Output Copy

7 8 16 
2 3 5 8 
 
34 75 86 55 88 18 8 10