IITWPC4D - Arrangement Validity

n persons are standing in a line. Height of each person is between 1 and n and height of each person is distinct. 

You a given array A where A[i] denotes how many persons are before i_th person having heights greater than H[i]. eg. For person 2, person 1 is considered before him. If A is given to be [0, 1] then one valid arrangements of height could be [2, 1] as number of persons having height > 1 before 2 are 1 because H[1] > H[2]

You have to find out whether this array can be valid for some arrangement of persons. If you can uniquely do so, then find out the array H. Otherwise output -1.

Input

First line contains T : number of test cases. (1 <= T <= 20).

For each test First line contains an integer n. (1 <= n <= 10^5)

Next line contains n space separated integers denoting A[i]. (0 <= A[i] <= n)

Output

For each test case output single line 

If there is a unique way of H. Then print n space separated integers in the line.

Otherwise output -1.

In starting of each test case also put "Test : testNumber" (without quotes). Note that there is a space before colon and one space after colon.

Example

Input:
2
3
0 1 1
3
0 1 0 Output: Test : 1
3 1 2
Test : 2
2 1 3

Added by:praveen123
Date:2014-01-31
Time limit:3s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:IITK ACA CSE online judge

hide comments
2019-07-27 06:45:00
Can we really have multiple ways for H?
2018-03-02 14:52:58
pbds rocks!
2014-05-24 07:35:05 RIVU DAS
Finally AC!!
2014-03-25 09:49:01 007: Name stolen
@praveen123
can u check my submission : http://www.spoj.com/files/src/11322713/

i have checked for over more than 100 test cases but still WA

Last edit: 2014-03-25 09:49:14
2014-02-08 21:59:34 Ujjwal Prakash
Nice problem with good test cases. Similar problem gave AC but this gave TLE
2014-02-04 00:47:43 praveen123
@bloody_looser Test data was wrongly uploaded, Updated now.
2014-02-04 00:46:16 shiv prasad chabarval
is there any problem with i/o format. praveen123 plz tell me why i am getting WA
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.