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
vietnamican: 2019-03-27 04:42:43

This problem just need O(n)

agrawal117: 2019-03-20 11:20:14

again and again TLE coming why?? pls help !!

anirudnits: 2019-01-02 19:22:18

@vivek_shah98 Thanks :)

vivek_shah98: 2018-10-07 08:21:06

I solved this problem in O(nlog(n)) using Policy based data structures on indexes..

rajcoolaryan: 2018-06-22 14:20:25

if you know vector .. u are done with this ques ..

aman_sachin200: 2018-06-05 17:20:56

Nice One!!!BIT+Binary Search :)!!!Solve the rookie problem first..

sandeep_123: 2017-12-15 14:05:27

Great problem !! did with vector erase, without segment tree :D complexity - O(N*log(N))

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

Added by:Shikhar
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