F. Skyscape
time limit per test
4 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

You are given a permutation $$$a$$$ of length $$$n$$$$$$^{\text{∗}}$$$.

We say that a permutation $$$b$$$ of length $$$n$$$ is good if the two permutations $$$a$$$ and $$$b$$$ can become the same after performing the following operation at most $$$n$$$ times (possibly zero):

  • Choose two integers $$$l, r$$$ such that $$$1 \le l \lt r \le n$$$ and $$$a_r = \min(a_l, a_{l + 1}, \ldots, a_r)$$$.
  • Cyclically shift the subsegment $$$[a_l, a_{l + 1}, \ldots, a_r]$$$ one position to the right. In other words, replace $$$a$$$ with $$$[a_1, \ldots, a_{l - 1}, \; a_r, a_l, a_{l + 1}, \ldots, a_{r - 1}, \; a_{r + 1}, \ldots, a_n]$$$.

You are also given a permutation $$$c$$$ of length $$$n$$$ where some elements are missing and represented by $$$0$$$.

You need to find a good permutation $$$b_1, b_2, \ldots, b_n$$$ such that $$$b$$$ can be formed by filling in the missing elements of $$$c$$$ (i.e., for all $$$1 \le i \le n$$$, if $$$c_i \ne 0$$$, then $$$b_i = c_i$$$). If it is impossible, output $$$-1$$$.

$$$^{\text{∗}}$$$A permutation of length $$$n$$$ is an array consisting of $$$n$$$ distinct integers from $$$1$$$ to $$$n$$$ in arbitrary order. For example, $$$[2,3,1,5,4]$$$ is a permutation, but $$$[1,2,2]$$$ is not a permutation ($$$2$$$ appears twice in the array), and $$$[1,3,4]$$$ is also not a permutation ($$$n=3$$$ but there is $$$4$$$ in the array).

Input

Each test contains multiple test cases. The first line contains the number of test cases $$$t$$$ ($$$1 \le t \le 10^4$$$). The description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 5 \cdot 10^5$$$).

The second line of each test case contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$). It is guaranteed that $$$a$$$ is a permutation of length $$$n$$$.

The third line of each test case contains $$$n$$$ integers $$$c_1, c_2, \ldots, c_n$$$ ($$$0 \le c_i \le n$$$). It is guaranteed that the elements of $$$c$$$ that are not $$$0$$$ are distinct.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$5 \cdot 10^5$$$.

Output

For each test case:

  • If it is impossible to find such a good permutation $$$b$$$, output a single integer $$$-1$$$.
  • Otherwise, output $$$n$$$ integers $$$b_1, b_2, \ldots, b_n$$$ — the good permutation $$$b$$$ you've found. You need to ensure that for all $$$1 \le i \le n$$$, if $$$c_i \ne 0$$$, then $$$b_i = c_i$$$. If there are multiple answers, output any of them.
Example
Input
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
Output
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
Note

In the first test case, $$$b = [1, 2]$$$ is a valid answer since after performing the following operation, $$$a$$$ and $$$b$$$ will become the same:

  • Choose $$$l = 1, r = 2$$$ and cyclically shift the subsegment $$$[a_1, a_2]$$$ one position to the right. Then $$$a$$$ will become $$$[1, 2]$$$.

In the second test case, $$$b = [2, 3, 4, 1]$$$ is a valid answer since after performing the following operation, $$$a$$$ and $$$b$$$ will become the same:

  • Choose $$$l = 1, r = 2$$$ and cyclically shift the subsegment $$$[a_1, a_2]$$$ one position to the right. Then $$$a$$$ will become $$$[2, 3, 4, 1]$$$.

In the third test case, $$$b = [1, 3, 2, 4, 5]$$$ is a valid answer since after performing the following operation, $$$a$$$ and $$$b$$$ will become the same:

  • Choose $$$l = 1, r = 3$$$ and cyclically shift the subsegment $$$[a_1, a_2, a_3]$$$ one position to the right. Then $$$a$$$ will become $$$[1, 3, 2, 5, 4]$$$.
  • Choose $$$l = 4, r = 5$$$ and cyclically shift the subsegment $$$[a_4, a_5]$$$ one position to the right. Then $$$a$$$ will become $$$[1, 3, 2, 4, 5]$$$.

In the fourth test case, $$$b = [3, 2, 1, 5, 4]$$$ is a valid answer since $$$a$$$ and $$$b$$$ are already the same.

In the fifth test case, it is impossible to find such a good permutation $$$b$$$, so you should output $$$-1$$$.

In the sixth test case, $$$b = [3, 2, 1, 5, 4, 6]$$$ is a valid answer since after performing the following operation, $$$a$$$ and $$$b$$$ will become the same:

  • Choose $$$l = 2, r = 4$$$ and cyclically shift the subsegment $$$[a_2, a_3, a_4]$$$ one position to the right. Then $$$a$$$ will become $$$[3, 2, 5, 6, 1, 4]$$$.
  • Choose $$$l = 3, r = 5$$$ and cyclically shift the subsegment $$$[a_3, a_4, a_5]$$$ one position to the right. Then $$$a$$$ will become $$$[3, 2, 1, 5, 6, 4]$$$.
  • Choose $$$l = 5, r = 6$$$ and cyclically shift the subsegment $$$[a_5, a_6]$$$ one position to the right. Then $$$a$$$ will become $$$[3, 2, 1, 5, 4, 6]$$$.