F. Небосвод
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам дана перестановка $$$a$$$ длины $$$n$$$$$$^{\text{∗}}$$$.

Скажем, что перестановка $$$b$$$ длины $$$n$$$ является хорошей, если две перестановки $$$a$$$ и $$$b$$$ могут стать одинаковыми после выполнения следующей операции не более $$$n$$$ раз (возможно, ноль):

  • Выберите два целых числа $$$l, r$$$ такие, что $$$1 \le l \lt r \le n$$$ и $$$a_r = \min(a_l, a_{l + 1}, \ldots, a_r)$$$.
  • Циклически сдвиньте подотрезок $$$[a_l, a_{l + 1}, \ldots, a_r]$$$ на одну позицию вправо. Другими словами, замените $$$a$$$ на $$$[a_1, \ldots, a_{l - 1}, \; a_r, a_l, a_{l + 1}, \ldots, a_{r - 1}, \; a_{r + 1}, \ldots, a_n]$$$.

Вам также дана перестановка $$$c$$$ длины $$$n$$$, в которой некоторые элементы отсутствуют и представлены как $$$0$$$.

Вам нужно найти хорошую перестановку $$$b_1, b_2, \ldots, b_n$$$, такую что $$$b$$$ может быть сформирована путем заполнения отсутствующих элементов в $$$c$$$ (т.е. для всех $$$1 \le i \le n$$$, если $$$c_i \ne 0$$$, то $$$b_i = c_i$$$). Если это невозможно, выведите $$$-1$$$.

$$$^{\text{∗}}$$$Перестановкой длины $$$n$$$ является массив, состоящий из $$$n$$$ различных целых чисел от $$$1$$$ до $$$n$$$ в произвольном порядке. Например, $$$[2,3,1,5,4]$$$ — перестановка, но $$$[1,2,2]$$$ не перестановка ($$$2$$$ встречается в массиве дважды) и $$$[1,3,4]$$$ тоже не перестановка ($$$n=3$$$, но в массиве встречается $$$4$$$).

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2 \le n \le 5 \cdot 10^5$$$).

Вторая строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$). Гарантируется, что $$$a$$$ является перестановкой длины $$$n$$$.

Третья строка каждого набора входных данных содержит $$$n$$$ целых чисел $$$c_1, c_2, \ldots, c_n$$$ ($$$0 \le c_i \le n$$$). Гарантируется, что элементы $$$c$$$, которые не равны $$$0$$$, различны.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$5 \cdot 10^5$$$.

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

Для каждого набора входных данных:

  • Если невозможно найти такую хорошую перестановку $$$b$$$, выведите одно целое число $$$-1$$$.
  • В противном случае выведите $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$ — хорошую перестановку $$$b$$$, которую вы нашли. Вы должны убедиться, что для всех $$$1 \le i \le n$$$, если $$$c_i \ne 0$$$, то $$$b_i = c_i$$$. Если есть несколько ответов, выведите любой из них.
Пример
Входные данные
9
2
2 1
1 2
4
3 2 4 1
2 0 0 1
5
3 2 1 5 4
1 3 0 0 0
5
3 2 1 5 4
3 2 1 5 4
5
3 2 1 5 4
3 2 5 1 4
6
3 5 6 2 1 4
0 2 0 5 0 0
6
3 5 6 2 1 4
0 2 0 6 4 0
9
6 9 2 4 1 7 8 3 5
0 2 5 9 0 0 0 8 0
9
8 5 3 9 1 7 4 6 2
0 0 8 0 7 0 4 0 2
Выходные данные
1 2
2 3 4 1
1 3 2 4 5
3 2 1 5 4
-1
3 2 1 5 4 6
-1
-1
1 3 8 5 7 9 4 6 2
Примечание

В первом наборе входных данных $$$b = [1, 2]$$$ является допустимым ответом, поскольку после выполнения следующей операции $$$a$$$ и $$$b$$$ станут одинаковыми:

  • Выберите $$$l = 1, r = 2$$$ и циклически сдвиньте подотрезок $$$[a_1, a_2]$$$ на одну позицию вправо. Тогда $$$a$$$ станет $$$[1, 2]$$$.

Во втором наборе входных данных $$$b = [2, 3, 4, 1]$$$ является допустимым ответом, поскольку после выполнения следующей операции $$$a$$$ и $$$b$$$ станут одинаковыми:

  • Выберите $$$l = 1, r = 2$$$ и циклически сдвиньте подотрезок $$$[a_1, a_2]$$$ на одну позицию вправо. Тогда $$$a$$$ станет $$$[2, 3, 4, 1]$$$.

В третьем наборе входных данных $$$b = [1, 3, 2, 4, 5]$$$ является допустимым ответом, поскольку после выполнения следующей операции $$$a$$$ и $$$b$$$ станут одинаковыми:

  • Выберите $$$l = 1, r = 3$$$ и циклически сдвиньте подотрезок $$$[a_1, a_2, a_3]$$$ на одну позицию вправо. Тогда $$$a$$$ станет $$$[1, 3, 2, 5, 4]$$$.
  • Выберите $$$l = 4, r = 5$$$ и циклически сдвиньте подотрезок $$$[a_4, a_5]$$$ на одну позицию вправо. Тогда $$$a$$$ станет $$$[1, 3, 2, 4, 5]$$$.

В четвертом наборе входных данных $$$b = [3, 2, 1, 5, 4]$$$ является допустимым ответом, поскольку $$$a$$$ и $$$b$$$ уже одинаковы.

В пятом наборе входных данных невозможно найти такую хорошую перестановку $$$b$$$, поэтому вы должны вывести $$$-1$$$.

В шестом наборе входных данных $$$b = [3, 2, 1, 5, 4, 6]$$$ является допустимым ответом, поскольку после выполнения следующей операции $$$a$$$ и $$$b$$$ станут одинаковыми:

  • Выберите $$$l = 2, r = 4$$$ и циклически сдвиньте подотрезок $$$[a_2, a_3, a_4]$$$ на одну позицию вправо. Тогда $$$a$$$ станет $$$[3, 2, 5, 6, 1, 4]$$$.
  • Выберите $$$l = 3, r = 5$$$ и циклически сдвиньте подотрезок $$$[a_3, a_4, a_5]$$$ на одну позицию вправо. Тогда $$$a$$$ станет $$$[3, 2, 1, 5, 6, 4]$$$.
  • Выберите $$$l = 5, r = 6$$$ и циклически сдвиньте подотрезок $$$[a_5, a_6]$$$ на одну позицию вправо. Тогда $$$a$$$ станет $$$[3, 2, 1, 5, 4, 6]$$$.