A. A Highly Constrained Problem...
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given $$$2$$$ arrays $$$A$$$ and $$$B$$$ of length $$$n$$$. You need to determine if there exists a permutation $$$P$$$ such that the following constraints are satisfied for all $$$1 \leq i \leq n$$$:

  • The longest strictly increasing subsequence of $$$P$$$ that ends in $$$P_i$$$ has length $$$A_i$$$.
  • The longest strictly increasing subsequence of $$$P$$$ that starts from $$$P_i$$$ has length $$$B_i$$$.
If there doesn't exist any such permutation print $$$-1$$$. Else print any permutation that satisfies these constraints.
Input

Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 2\times 10^5$$$), the number of test cases.

For each of the test case,

The first line contains a single integer $$$n$$$ ($$$1 \leq n \leq 5\times 10^5$$$).

The second line contains $$$n$$$ space separated integers $$$A_1, A_2, \dots, A_n$$$ denoting the elements of $$$A$$$ ($$$1 \leq A_i \leq i)$$$.

The third line contains $$$n$$$ space separated integers $$$B_1,B_2,\dots, B_n$$$ denoting the elements of $$$B$$$ ($$$1 \leq B_i \leq n-i+1$$$).

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

Output

For each of the test case, if there doesn't exist any permutation print $$$-1$$$. If there exists, print any valid permutation.

Example
Input
5
1
1
1
3
1 1 2
1 2 1
3
1 2 3
1 1 1
5
1 1 2 3 2
3 3 2 1 1
5
1 2 2 2 2
2 2 1 2 1
Output
1 
3 1 2 
-1
3 1 4 5 2 
-1
Note

For test case $$$4$$$,

  • LIS ending in $$$P_1$$$ is $$$[3]$$$, thus $$$A_1=1$$$.
  • LIS ending in $$$P_2$$$ is $$$[1]$$$, thus $$$A_2=1$$$.
  • LIS ending in $$$P_3$$$ is $$$[3,4]$$$, thus $$$A_3=2$$$.
  • LIS ending in $$$P_4$$$ is $$$[3,4,5]$$$, thus $$$A_4=3$$$.
  • LIS ending in $$$P_5$$$ is $$$[1,2]$$$, thus $$$A_5=2$$$.

Similarly

  • LIS starting in $$$P_1$$$ is $$$[3,4,5]$$$, thus $$$B_1=3$$$.
  • LIS starting in $$$P_2$$$ is $$$[1,4,5]$$$, thus $$$B_2=3$$$.
  • LIS starting in $$$P_3$$$ is $$$[4,5]$$$, thus $$$B_3=2$$$.
  • LIS starting in $$$P_4$$$ is $$$[5]$$$, thus $$$B_4=1$$$.
  • LIS starting in $$$P_5$$$ is $$$[2]$$$, thus $$$B_5=1$$$.