F. Skyscapetime limit per test4 secondsmemory limit per test512 megabytesinputstandard inputoutputstandard 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 < 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). InputEach 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$$$. OutputFor 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. ExampleInput922 11 243 2 4 12 0 0 153 2 1 5 41 3 0 0 053 2 1 5 43 2 1 5 453 2 1 5 43 2 5 1 463 5 6 2 1 40 2 0 5 0 063 5 6 2 1 40 2 0 6 4 096 9 2 4 1 7 8 3 50 2 5 9 0 0 0 8 098 5 3 9 1 7 4 6 20 0 8 0 7 0 4 0 2Output1 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
NoteIn 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]$$$.