Problem L. Limited permutation ≡

Statement

There are two integer arrays A and B, of length N each.

Your program must generate lexicographically minimal permutation of A, satisfying conditions:

A_i ≤ B_i, i = 1, 2, …, N

Input format

Input contains integer N, followed by 2 ⋅ N integers: array A, then array B.

Output format

Output must contain N integers — resulting permutation.

If the solution does not exist, output a single number  − 1.

Constraints

0 ≤ A_i, B_i ≤ 10⁹, 1 ≤ N ≤ 2 ⋅ 10⁵

Sample tests

5
1 9 3 7 5
9 3 9 1 9

5 3 7 1 9

5
1 9 3 7 5
9 3 3 1 7

-1

Explanation

Дополним элементы массива B номерами их индексов. Полученные в результате пары {значение, индекс} будем называть корзинами.

Отсортируем массивы A и B по убыванию значений. Заведем изначально пустое множество Q, предназначенное для хранения корзин.

Выберем наибольший элемент A_i и извлечем из B все корзины, значения которых позволяют вместить в них такой элемент.

Все извлеченные корзины из B перекладываем в Q.

Далее среди отложенных корзин из Q выберем ту, у которой индекс максимально возможный.

Таким образом, элементы из A, которые могли бы поместиться в те же корзины, что и A_i,
но имеющие меньшие значения, окажутся в более ранних позициях.

Если в качестве Q использовать двоичную кучу,
получим сложность алгоритма равную O(N ⋅ log(N)).