RLTOUR - Robert Langdon & Florence

As a token of thanks for his help, Elizabeth Sinskey has gifted Robert Langdon an amazing set of Russian dolls. The dolls have the property that if doll A has height HA and doll B has height HB, then B can fit inside A if HA >= HB.

Robert noted the heights of the dolls (two dolls can have same height), and then arranged the dolls in a line beautifully. For each doll he noted down the number of dolls that are before this doll in the line and can contain this doll. He wrote this down on another piece of paper.

Accidentally, the dolls fell out of line, and Robert wants to arrange them back beautifully. Given the two pieces of information (heights of the dolls and number of dolls before this in line that can contain this doll), can you rearrange the dolls beautifully?

Input

First line contains T, number of test cases.

Each test case consists of 3 lines:

First line of each test case has a single number N, number of dolls.

Second line contains array H, space separated array of size N containing the heights of dolls.

Third line contains array C, space separated array of size N, C[i] indicating number of dolls before this in the beautiful arrangement that can contain doll i.

Output

For each test case, output a single line containing the heights of dolls in order as they were when Robert arranged them beautifully.

Assume that a valid solution always exists.

Example

Input:
2
3
12 13 14
0 0 2
3
12 14 13
0 1 0

Output:
13 14 12
13 12 14

Explanation

For the first case, (arrangement 13, 14, 12) 13 and 14 cannot be contained by any doll prior to them, but 12 can be put in doll 13 as well as doll 14, hence the array 0 0 2.

For the second case, (arrangement 13, 12, 14) 12 can be contained in 13, hence the array 0 1 0.

Constraints

1 <= T <= 500

1 <= N <= 500

1 <= H[i] <= 109


Added by:Piyush Kumar
Date:2014-01-19
Time limit:2s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:IIT Bombay Coding GC

hide comments
2014-10-05 10:52:14 Govind Lahoti
nice problem
2014-03-20 12:35:52 innovolt
gud1........AC in 1 go
2014-02-19 16:47:03 Ouditchya Sinha
@sankar: This might be possible if the judge used here is standard & not exact. Read more about "Test case judge" here: http://www.spoj.com/tutorials/PS/
2014-02-19 15:34:08 sankar
A solution without a '\n' in between cases is getting accepted. What does that mean
2014-02-19 11:10:55 Ouditchya Sinha
@Amit Jain: It seems you are referring to this problem, http://www.spoj.com/problems/QUE1/
Both are different, read the question carefully, all the best! :)
2014-02-09 21:22:45 The Alchemist
luv u STL :)
2014-02-06 18:34:28 anurag garg
amit jain your test case is not valid.....
2014-02-04 18:47:26 Amit Jain
I think, the Ques have multiple solutions
for
1
5
33 11 22 44 55
0 2 1 1 0
there are two possible solutions
33 22 11 55 44 (0 1 2 0 1)
and
44 22 11 33 55. (0 1 2 1 0)

Last edit: 2014-02-04 18:48:33
2014-01-29 15:00:17 Bhavik
C's built-in sort fuction is a lot slower than C++'s sort function!!!
2014-01-26 13:45:53 RIVU DAS
Any tricky test cases please!!!
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.