Перестановкой длины \(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\).
Выходные данные
В случае если Неко совершил ошибку и массива \(a\) и перестановки \(p\), приводящих к описанным \(b'\) и \(c'\) не существует, то выведите -1, иначе выведите \(n\) целых чисел \(a_i\) (\(1 \le a_i \le 10^9\)), обозначающих элементы массива \(a\).
В случае если существует несколько возможных решений, выведите любое из них.
Примечание
Первый пример разобран в условии задачи.
В третьем примере для \(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]\)
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
4 5 3 5
6 7 4 6
|
3 4 6 5 7
|
|
2
|
3
2 4
3 2
|
-1
|
|
3
|
8
2 3 1 1 2 4 3
3 4 4 2 5 5 4
|
3 4 5 2 1 4 3 2
|