KOILINE - Line up


N people are lined up in a straight line to enter a concert. Each person in this line knows how many people in front have shorter or same heights. Let's call the sequence representing these numbers S. So in other words, S[i] means that there are S[i] people in front of the ith person who have shorter or same heights than that of person i. 

Given the heights of N people and a sequence S, determine the correct order of people lined up. (left is front)   

Input

The first line of the input is an integer N. (1<=N<=100,000)

The next N lines each consists of one integer H. (1<=H<=2*10^9) These N integers are the heights of people lined up.

Then, sequence S is given in a single line, separated by a space.  

Output

Determine the correct ordering of people lined up. Total of N lines should be output. The integer on the ith line represents the height of the ith person in the line. 

Example

Input:
12
120
167
163
172
145
134
182
155
167
120
119
156
0 1 0 0 3 2 6 7 4 6 9 4
Output: 134
167
120
119
156
120
167
182
155
163
172
145

hide comments
Rafail Loizou: 2020-09-11 11:31:33

forgetting to return the answer cost me a lot of submissions XD... always remember to return your binary searches result in any case XD

smso: 2018-07-30 12:57:20

hint: look from the back of sequence S, use segment tree to get over TLE

Utkarsh Agarwal: 2015-05-26 02:19:46

accepted !! :) changed two arrays of length 10^5 from long int to int, but the time it took to run increased instead :P same algo. same code :P

Last edit: 2015-05-26 02:27:23
Rishav Goyal: 2014-04-30 14:51:51

woe !! heights do fit in int!! moreover more implementation !! huh!! finally AC!!

Dario Sindicic: 2014-03-01 13:07:16

O( N*lgN*lgN) pass

:D: 2012-05-22 13:44:28

heights DO fit in int. I was reading them into that format in my ACC submission.

charvi: 2011-09-30 06:32:54

I have done KOILINE but for the same code I am getting TLE for SSEQ and orders

Santiago Palacio: 2011-06-13 21:26:54

@Ashish Massand: 2*10^9 < 2^63, so they do fit.

Ashish Massand: 2011-06-13 08:11:09

The heights don't fit in int they fit in long long int even though in the specification it is said h <= 2*10^9


Added by:Lawl
Date:2011-06-02
Time limit:0.703s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:2011 KOI Regional