Erdős and Szekeres Sequence Reconstruction

$X$ is a sequence that lists the numbers $1$ through $N$, each exactly once. Take some entries of $X$ in their original order. If the values keep growing, the entries form an increasing subsequence; if they keep shrinking, they form a decreasing subsequence. For example, $(5, 7, 8)$ is an increasing subsequence of $(4, 5, 3, 7, 6, 2, 8, 1)$.

Paul Erdős and George Szekeres proved that $X$ always contains an increasing subsequence of length at least $\sqrt{N}$ or a decreasing subsequence of length at least $\sqrt{N}$. The sequence above contains the decreasing subsequence $(5, 3, 2, 1)$ of length 4.

Two values are defined for each $i$.

• $A_i$ is the maximum length of an increasing subsequence whose largest number is $X_i$.
• $B_i$ is the maximum length of a decreasing subsequence whose largest number is $X_i$.

The largest number of an increasing subsequence is its last entry, so $A_i$ equals the maximum length of an increasing subsequence that ends at $X_i$. The largest number of a decreasing subsequence is its first entry, so $B_i$ equals the maximum length of a decreasing subsequence that starts at $X_i$.

For $X = (4, 5, 3, 7, 6, 2, 8, 1)$ the values are:

The pair $(A_i, B_i)$ differs for every $i$, and that forces $A_i$ or $B_i$ to be at least $\sqrt{N}$ for some $i$.

Given $A$ and $B$, reconstruct $X$. The answer must list the numbers $1$ through $N$ exactly once each. If several sequences are possible, print the lexicographically smallest one: make $X_0$ as small as possible, then make $X_1$ as small as possible among what is left, and so on.

The first line holds the number of test cases $T$. Each test case takes three lines.

The first line holds one integer $N$. The second line holds $A_0, A_1, \ldots, A_{N-1}$ separated by spaces. The third line holds $B_0, B_1, \ldots, B_{N-1}$ separated by spaces.

Limits

• $1 \le T \le 30$
• $1 \le N \le 20$
• $A_i$ and $B_i$ are positive integers.
• At least one valid $X$ exists.

For each test case print one line with Case #x: followed by $X_0, X_1, \ldots, X_{N-1}$ separated by spaces. Here $x$ is the test case number, counting from 1.