E. Neko and Flashback
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

A permutation of length $k$ is a sequence of $k$ integers from $1$ to $k$ containing each integer exactly once. For example, the sequence $[3, 1, 2]$ is a permutation of length $3$.

When Neko was five, he thought of an array $a$ of $n$ positive integers and a permutation $p$ of length $n - 1$. Then, he performed the following:

• Constructed an array $b$ of length $n-1$, where $b_i = \min(a_i, a_{i+1})$.
• Constructed an array $c$ of length $n-1$, where $c_i = \max(a_i, a_{i+1})$.
• Constructed an array $b'$ of length $n-1$, where $b'_i = b_{p_i}$.
• Constructed an array $c'$ of length $n-1$, where $c'_i = c_{p_i}$.

For example, if the array $a$ was $[3, 4, 6, 5, 7]$ and permutation $p$ was $[2, 4, 1, 3]$, then Neko would have constructed the following arrays:

• $b = [3, 4, 5, 5]$
• $c = [4, 6, 6, 7]$
• $b' = [4, 5, 3, 5]$
• $c' = [6, 7, 4, 6]$

Then, he wrote two arrays $b'$ and $c'$ on a piece of paper and forgot about it. 14 years later, when he was cleaning up his room, he discovered this old piece of paper with two arrays $b'$ and $c'$ written on it. However he can't remember the array $a$ and permutation $p$ he used.

In case Neko made a mistake and there is no array $a$ and permutation $p$ resulting in such $b'$ and $c'$, print -1. Otherwise, help him recover any possible array $a$.

Input

The first line contains an integer $n$ ($2 \leq n \leq 10^5$) — the number of elements in array $a$.

The second line contains $n-1$ integers $b'_1, b'_2, \ldots, b'_{n-1}$ ($1 \leq b'_i \leq 10^9$).

The third line contains $n-1$ integers $c'_1, c'_2, \ldots, c'_{n-1}$ ($1 \leq c'_i \leq 10^9$).

Output

If Neko made a mistake and there is no array $a$ and a permutation $p$ leading to the $b'$ and $c'$, print -1. Otherwise, print $n$ positive integers $a_i$ ($1 \le a_i \le 10^9$), denoting the elements of the array $a$.

If there are multiple possible solutions, print any of them.

Examples
Input
5
4 5 3 5
6 7 4 6

Output
3 4 6 5 7

Input
3
2 4
3 2

Output
-1

Input
8
2 3 1 1 2 4 3
3 4 4 2 5 5 4

Output
3 4 5 2 1 4 3 2

Note

The first example is explained is the problem statement.

In the third example, for $a = [3, 4, 5, 2, 1, 4, 3, 2]$, a possible permutation $p$ is $[7, 1, 5, 4, 3, 2, 6]$. In that case, Neko would have constructed the following arrays:

• $b = [3, 4, 2, 1, 1, 3, 2]$
• $c = [4, 5, 5, 2, 4, 4, 3]$
• $b' = [2, 3, 1, 1, 2, 4, 3]$
• $c' = [3, 4, 4, 2, 5, 5, 4]$