4.2 Map ka map ka map....

Score: 15pts

Time Limit: 5.00 sec

You have an array B representing the frequencies of elements, and your goal is to find the smallest possible array A such that:

- The elements of A are between 1 and 10^5.

- The frequency array of A is equal to B.

If it's not possible to create such an array A, print -1.

Note: In comparing two arrays X and Y, the lexicographically smaller one is determined by comparing the elements at the first index where they differ, with the smaller element indicating the smaller array.

For example, if A = [4, 7, 4, 11, 2, 7, 7], the frequency array B = [2, 3, 2, 1, 1, 3, 3] so

The frequency array of A is the array B of size N such that B[i] = frequency of element A[i] in A.

- The elements of A are between 1 and 10^5.

- The frequency array of A is equal to B.

If it's not possible to create such an array A, print -1.

Note: In comparing two arrays X and Y, the lexicographically smaller one is determined by comparing the elements at the first index where they differ, with the smaller element indicating the smaller array.

For example, if A = [4, 7, 4, 11, 2, 7, 7], the frequency array B = [2, 3, 2, 1, 1, 3, 3] so

The frequency array of A is the array B of size N such that B[i] = frequency of element A[i] in A.

Constraints

1 ≤ T ≤ 10^5 (number of test cases)

1 ≤ N ≤ 10^5 (size of the array)

1 ≤ Bi ≤ 10^5 (frequency array elements)

The sum of N over all test cases won't exceed 10^6.

1 ≤ N ≤ 10^5 (size of the array)

1 ≤ Bi ≤ 10^5 (frequency array elements)

The sum of N over all test cases won't exceed 10^6.

Input Format

The first line contains an integer T, the number of test cases.

For each test case:

The first line contains an integer N, the size of the array.

The second line contains N space-separated integers, which make up the frequency array B.

For each test case:

The first line contains an integer N, the size of the array.

The second line contains N space-separated integers, which make up the frequency array B.

Output Format

For each test case, output the lexicographically smallest array A of size N that matches the given frequency array B. If no such array exists, print -1.

Example 1

Input:

5

5

2 3 3 3 2

5

1 1 1 1 1

5

5 5 5 5 5

3

1 2 4

8

1 3 2 3 2 2 2 3

Output:

1 2 2 2 1

1 2 3 4 5

1 1 1 1 1

-1

1 2 3 2 3 4 4 2

Explanation:

Test case 1:

- The lexicographically smallest array A having the given frequency array B is A = [1, 2, 2, 2, 1].

- The element 1 (A1) and 5 (A5) have frequency 2, while 2 (A2), 3 (A3), and 4 (A4) have frequency 3.

Test case 2:

- The lexicographically smallest array A having the given frequency array B is A = [1, 2, 3, 4, 5].

- Each element in A has frequency 1.

Test case 3:

- The lexicographically smallest array A having the given frequency array B is A = [1, 1, 1, 1, 1].

- Each element in A has frequency 5.

Test case 4:

- No possible array A exists having the given frequency array B.

5

5

2 3 3 3 2

5

1 1 1 1 1

5

5 5 5 5 5

3

1 2 4

8

1 3 2 3 2 2 2 3

Output:

1 2 2 2 1

1 2 3 4 5

1 1 1 1 1

-1

1 2 3 2 3 4 4 2

Explanation:

Test case 1:

- The lexicographically smallest array A having the given frequency array B is A = [1, 2, 2, 2, 1].

- The element 1 (A1) and 5 (A5) have frequency 2, while 2 (A2), 3 (A3), and 4 (A4) have frequency 3.

Test case 2:

- The lexicographically smallest array A having the given frequency array B is A = [1, 2, 3, 4, 5].

- Each element in A has frequency 1.

Test case 3:

- The lexicographically smallest array A having the given frequency array B is A = [1, 1, 1, 1, 1].

- Each element in A has frequency 5.

Test case 4:

- No possible array A exists having the given frequency array B.