B. Combining Arrays
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Timmy has two arrays $$$A$$$ and $$$B$$$, both of length $$$n$$$. It is guaranteed that when $$$A$$$ and $$$B$$$ are concatenated, they form a permutation of the numbers $$$1 \dots 2n$$$. He wants to create a new array $$$C$$$ by performing the following operation $$$2n$$$ times: choose either $$$A$$$ or $$$B$$$ if it still has elements, remove the element at the beginning of the chosen array, and append that element to the end of $$$C$$$. Of all ways that Timmy can create an array $$$C$$$ with these operations, he wants to find the lexicographically minimal possible one.

An array $$$a$$$ is lexicographically less than an array $$$b$$$ if, at the first position where $$$a$$$ and $$$b$$$ differ, the element of $$$a$$$ in this position is less than the element of $$$b$$$ in this position.

Input

The first line contains a single integer $$$n$$$ $$$(1 \leq n \leq 10^5)$$$. The second line contains $$$n$$$ space-separated integers $$$A_1, A_2, \dots, A_n$$$. The third line contains $$$n$$$ space-separated integers $$$B_1, B_2, \dots, B_n$$$.

Output

Print $$$2n$$$ space-separated integers, the elements of the lexicographically minimal $$$C$$$.

Examples
Input
3
1 2 3
4 5 6
Output
1 2 3 4 5 6
Input
5
1 3 5 7 9
2 4 6 8 10
Output
1 2 3 4 5 6 7 8 9 10
Input
7
6 10 4 2 13 12 7
9 8 11 3 5 1 14
Output
6 9 8 10 4 2 11 3 5 1 13 12 7 14
Note

For the first sample, Timmy can first take $$$1, 2, $$$ and $$$3$$$ from $$$A$$$. Since $$$A$$$ is now empty, you must take $$$4, 5, $$$ and $$$6$$$ from $$$B$$$.

For the second sample, Timmy can alternate taking from $$$A$$$ and $$$B$$$.