QUE1 - Queue (Rookie)


There are N people standing in a Queue. You are given the height of each person and the number of people who are taller and standing ahead of him. You have to find the position of each person.

Input

First line conatins a single integer T, the number of test cases. It is followed by T test cases each of which contains 3 lines. First line of each test case contains a single integer N. Second line contains N integers representing the heights of these N people. Third line also contains N integers denoting the number of taller people standing ahead of him.

Output

Output one line for each test case which contains the heights of the N people in the order in which they are standing.

Constraints

0 < T <= 100
0 < N <= 1000

Expected Time Complexity = O(N2)

Example

Input:
1
5
33 11 22 44 55
0 2 1 1 0

Output:
33 22 11 55 44

Harder Version : Queue (Pro)


hide comments
ankkt16: 2019-02-17 12:10:37

ac at once :)
O(n).

dung199551: 2019-01-21 19:19:19

8 3 2 8 7 4 9 5
2 4 5 0 3 0 0 2
i think above testcase has result 4 8 9 5 3 2 8 7 but when i try the source code is accepted by this problem has result 4 8 8 5 3 2 9 7.
the number 8 has 2 higher than it but accepted result has only 1.

abhu: 2018-11-08 07:56:01

Good reading material : http://mathonline.wikidot.com/generating-permutations-with-inversion-sequences

Last edit: 2018-11-08 08:04:24
codiesam_007: 2018-06-04 23:56:03

My 150th !!
Great Question...n^2 is easier and gets accepted but nlogn is a bit difficult but a must try!

karthik1997: 2018-01-08 08:15:24

Man , struggled too hard to get an NlogN solution . Really good problem :)

Last edit: 2018-01-08 08:15:44
sandeep_123: 2017-12-15 11:46:07

A very good problem!!, simple iterative solution.

Last edit: 2017-12-15 11:59:34
leduchuybk: 2017-09-14 19:58:37

I dont know if anyone gets the wrong mistakes like me but warning.
You have more than one test case. so make sure you can print more than one result

sandip_coder: 2017-02-11 19:01:50

nice problem...
silly mistake getting 3 times Wrong answer..
finally accepted

Last edit: 2017-02-11 19:05:36
shaan001: 2016-09-19 14:09:33

platwnas: 2016-06-20 15:57:02
Cant understand the test case. Which way are the people looking ? And provide more test cases.

33 22 11 55 44
0 2 1 1 0
Why is this the answer. 33 has 55 and 44 ahead of him so it should be 2 and not zero and 11 should be 2 and not 1.


Its a queue...33 front and 44 rear and 11 is 2 not 1...read carefully

platwnas: 2016-06-20 15:57:02

Cant understand the test case. Which way are the people looking ? And provide more test cases.

33 22 11 55 44
0 2 1 1 0
Why is this the answer. 33 has 55 and 44 ahead of him so it should be 2 and not zero and 11 should be 2 and not 1.

Last edit: 2016-06-20 16:00:58

Added by:Shikhar
Date:2013-09-16
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64 PYTHON PYTHON3 PY_NBC
Resource:Directi Interview