QUE2 - Queue (Pro)


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 <= 20
0 < N <= 10000

Expected Time Complexity = O(N log N)

Example

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

Output:
33 22 11 55 44

Easier Version : Queue (Rookie)


hide comments
Piyush Agarwal: 2017-09-02 13:21:26

aexpo test case was helpful

Last edit: 2017-09-02 13:21:47
aexpo: 2017-07-25 16:33:58

Need some help!
Does taller mean strictly taller here?
If yes then the expected output for the case given below should be (10 9 8 9 8 7 6):
1
5
10 9 9 8 8 7 6
0 1 1 2 3 5 6
whereas my AC solution produces output (10 9 8 8 9 7 6).
Can anyone give a clarification on this? Thanx in advance

sonu: 2017-06-22 09:35:30

My O(n^2) solution is AC . Don't know how when expected is O(nlogn). :)
My solution uses Insertion sort

Last edit: 2017-06-22 09:40:29
sultania23: 2017-03-23 20:14:21

jst modified segment tree ....

AAKASH TYAGI: 2016-06-30 00:09:20

n (logn)^2 solution works only if BIT is used

enigmus: 2016-02-29 18:24:34

Trees!!!

Abhinandan Agarwal: 2015-10-22 22:26:15

my nlogn and n(logn)**2 solution both got acptd with same time - 0.18s .

Rang: 2015-06-08 12:06:04

Enjoyed proving the solution :)

ankit bisla: 2015-01-26 09:52:06

Enjoyed solving it :)


Added by:@ce
Date:2013-09-16
Time limit:0.100s-0.25s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Directi Interview