Neko and Flashback

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 ≤ n ≤ 10^5) — the number of elements in array a.

The second line contains n-1 integers b'_1, b'2, …, b'{n-1} (1 ≤ b'_i ≤ 10^9).

The third line contains n-1 integers c'_1, c'2, …, c'{n-1} (1 ≤ c'_i ≤ 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 ≤ a_i ≤ 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]

inputFormat

Input

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

The second line contains n-1 integers b'_1, b'2, …, b'{n-1} (1 ≤ b'_i ≤ 10^9).

The third line contains n-1 integers c'_1, c'2, …, c'{n-1} (1 ≤ c'_i ≤ 10^9).

outputFormat

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 ≤ a_i ≤ 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]

样例

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

2 5 4 3 4 1 2 3 

</p>