Pongos P52016

Each Christmas holidays, $n$ friends meet to celebrate a tradition. There are $n$ useless presents, which are called pongos. The pongos are wrapped up with newspaper, so at the beginning of the game the only available information for each pongo $i$ is $a_i$: how cool $i$ seems while it is wrapped up. Let $r_i$ be the real coolness of $i$. This real coolness is only known when the pongo is unwrapped. The higher the value of $a_i$, the cooler the pongo looks when wrapped. The higher $r_i$, the cooler it is when unwrapped.

The game goes as follows. The participants are numbered from 0 to $n-1$. At the beginning of the $j$-th round (from 0 to $n-1$), each of the first $j$ participants has an unwrapped pongo at his hands, which is seen by everybody. The round starts with the participant number $j$. He always takes the pongo that looks or is coolest according to the available information: if the pongo is still unchosen and therefore wrapped up, he uses $a_i$, and if the pongo is already on some participant’s hands, he uses $r_i$.

If a participant takes a wrapped pongo, he unwraps it and the game goes to the next round. If he takes a pongo from another participant, the participant that just lost his pongo takes the pongo that is or looks coolest among those that have not been chosen in the current round. The round continues like this until someone takes a wrapped pongo and unwraps it.

This game is deterministic. Can you tell the real coolness of the pongo that every person has at the end of the game?

Input

Input consists of several cases. Every case starts with $n$, followed by the $n$ integers $a_i$, followed by the $n$ integers $r_i$. You can assume $1 \le n \le 10^4$. All the values for $a_i$ and $r_i$ are distinct integers between $0$ and $2n-1$.

Output

For every case, print the $n$ integers $r_j$, where $r_j$ is the real coolness of the pongo at the hands of the $j$-th person at the end of the game.