E. Неко и флэшбеки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Перестановкой длины $$$k$$$ называется последовательность из $$$k$$$ целых чисел от $$$1$$$ до $$$k$$$, в которой каждое число встречается ровно один раз. Например последовательность $$$[3, 1, 2]$$$ является перестановкой длины $$$3$$$.

Когда Неко было пять лет, он придумал массив $$$a$$$ из $$$n$$$ положительных целых чисел и перестановку $$$p$$$ длины $$$n - 1$$$. Затем он выполнил следующее:

  • Составил массив $$$b$$$ длины $$$n-1$$$, где $$$b_i = \min(a_i, a_{i+1})$$$.
  • Составил массив $$$c$$$ длины $$$n-1$$$, где $$$c_i = \max(a_i, a_{i+1})$$$.
  • Составил массив $$$b'$$$ длины $$$n-1$$$, где $$$b'_i = b_{p_i}$$$.
  • Составил массив $$$c'$$$ длины $$$n-1$$$, где $$$c'_i = c_{p_i}$$$.

Например, если массив $$$a$$$ был равен $$$[3, 4, 6, 5, 7]$$$, а перестановка $$$p$$$ была равна $$$[2, 4, 1, 3]$$$, то Неко составил бы массивы следующим образом:

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

Затем он записал массивы $$$b'$$$ и $$$c'$$$ на бумажку, после чего благополучно о ней забыл. Спустя 14 лет, в процессе уборки своей комнаты, он обнаружил эту старую бумажку с массивами $$$b'$$$ и $$$c'$$$. К сожалению, Неко не смог вспомнить какой массив $$$a$$$ и перестановку $$$p$$$ он при этом использовал.

В случае если Неко ошибся, и массива $$$a$$$ и перестановки $$$p$$$, приводящим к таким $$$b'$$$ и $$$c'$$$ не существует, выведите -1. Иначе помогите восстановить ему любой возможный массив $$$a$$$.

Входные данные

Первая строка содержит одно целое число $$$n$$$ ($$$2 \leq n \leq 10^5$$$) — количество элементов в массиве $$$a$$$.

Вторая строка содержит $$$n-1$$$ целых чисел $$$b'_1, b'_2, \ldots, b'_{n-1}$$$ ($$$1 \leq b'_i \leq 10^9$$$).

Третья строка содержит $$$n-1$$$ целых чисел $$$c'_1, c'_2, \ldots, c'_{n-1}$$$ ($$$1 \leq c'_i \leq 10^9$$$).

Выходные данные

В случае если Неко совершил ошибку и массива $$$a$$$ и перестановки $$$p$$$, приводящих к описанным $$$b'$$$ и $$$c'$$$ не существует, то выведите -1, иначе выведите $$$n$$$ целых чисел $$$a_i$$$ ($$$1 \le a_i \le 10^9$$$), обозначающих элементы массива $$$a$$$.

В случае если существует несколько возможных решений, выведите любое из них.

Примеры
Входные данные
5
4 5 3 5
6 7 4 6
Выходные данные
3 4 6 5 7
Входные данные
3
2 4
3 2
Выходные данные
-1
Входные данные
8
2 3 1 1 2 4 3
3 4 4 2 5 5 4
Выходные данные
3 4 5 2 1 4 3 2
Примечание

Первый пример разобран в условии задачи.

В третьем примере для $$$a = [3, 4, 5, 2, 1, 4, 3, 2]$$$, возможная перестановка $$$p$$$ выглядит следующим образом $$$[7, 1, 5, 4, 3, 2, 6]$$$. В таком случае Неко построил бы следующие:

  • $$$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]$$$