SSEQ - Standing Sequence


Now that the two tribes met, a joint force was formed. Colonel Prateek was ordered to lead the force. He needs to instruct his men on how to stand. The n men in the force have been given ranks from 1(lowest) to n(highest) and on parade they should be lined up from left to right in increasing order of rank. He soon discovered that his elite commandos preferred to do the fighting, and leave the thinking to their superiors. So, when at the first roll call the soldiers lined up in fairly random order it was not because of their lack of discipline, but simply because they couldn’t work out how to form a line in correct order of ranks. Colonel Prateek was not at all amused, particularly as he soon found that none of the soldiers even remembered his own rank. Over the years of service every soldier had only learned which of the other soldiers were his superiors. But Colonel Prateek was not a man to give up easily when faced with a true military challenge. After a moment’s thought a solution of brilliant simplicity struck him and he issued the following order: "men, starting from the left, one by one, do: (step forward; go left until there is no superior to the left of you; get back in line).". This did indeed get the men sorted in a few minutes. The problem was solved... for the time being.

The next day, the soldiers came in exactly the same order as the day before, and had to be rearranged using the same method. History repeated. After some weeks, Colonel Prateek managed to force each of his soldiers to remember how many men he passed when going left, and thus make the sorting process even faster.

If you know how many positions each man has to walk to the left, can you try to find out what order of ranks the soldiers initially line up in?

Input

The first line of input contains an integer t<=50, the number of test cases. It is followed by t test cases, each consisting of 2 lines. The first line contains a single integer n (1<=n<=200000). The second line contains n space separated integers wi , denoting how far the ith soldier in line must walk to the left when applying Colonel Prateek’s algorithm.

Output

For each test case, output a single line consisting of n space separated integers - the ranks of the soldiers, given from left to right in their initial arrangement.

Example

Input:
2
3
0 1 0
5
0 1 2 0 1

Output:
2 1 3
3 2 1 5 4

hide comments
Sunil: 2015-05-04 09:24:11

nlogn with fast io gives TLE

Jaros³aw Meller: 2011-06-07 07:42:24

Can someone give me any hint? I have optimized my ORDERS solution, but still no luck with this one... 1.05 in ORDERS, TLE here...

Krzysztof Lewko: 2011-06-06 21:28:16

Only input optimalization is really required to get AC.

Aadit Prasad: 2011-03-20 22:15:13

For those suffering from TLEs, use faster I/O, helped me get AC.


Added by:Troika::Bytes
Date:2010-02-18
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: PERL6