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

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

hide comments
2020-09-11 11:31:33 Rafail Loizou
forgetting to return the answer cost me a lot of submissions XD... always remember to return your binary searches result in any case XD
2018-07-30 12:57:20
hint: look from the back of sequence S, use segment tree to get over TLE
2015-05-26 02:19:46 Utkarsh Agarwal
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
2014-04-30 14:51:51 Rishav Goyal
woe !! heights do fit in int!! moreover more implementation !! huh!! finally AC!!
2014-03-01 13:07:16 Dario Sindicic
O( N*lgN*lgN) pass
2012-05-22 13:44:28 :D
heights DO fit in int. I was reading them into that format in my ACC submission.
2011-09-30 06:32:54 charvi
I have done KOILINE but for the same code I am getting TLE for SSEQ and orders
2011-06-13 21:26:54 Santiago Palacio
@Ashish Massand: 2*10^9 < 2^63, so they do fit.
2011-06-13 08:11:09 Ashish Massand
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
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.