Erdős-Szekeres (Large)

$X$ is a sequence that uses each of the numbers $1$ through $N$ exactly once. An increasing subsequence of $X$ is a set of elements picked in order that grows from left to right, and a decreasing subsequence is one that shrinks from left to right. For example, $(5, 7, 8)$ is an increasing subsequence of $(4, 5, 3, 7, 6, 2, 8, 1)$.

Almost 80 years ago Paul Erdős and George Szekeres proved the following. Every such $X$ of length $N$ has an increasing subsequence of length at least $\sqrt{N}$ or a decreasing subsequence of length at least $\sqrt{N}$. For example, $(4, 5, 3, 7, 6, 2, 8, 1)$ has the decreasing subsequence $(5, 3, 2, 1)$ of length 4.

To demonstrate the theorem in a combinatorics class, two values were computed for every $i$.

• $A[i]$: the length of the longest increasing subsequence that has $X[i]$ as its largest element, that is, the longest increasing subsequence ending at $X[i]$.
• $B[i]$: the length of the longest decreasing subsequence that has $X[i]$ as its largest element, that is, the longest decreasing subsequence starting at $X[i]$.

The proof turns on the pair $(A[i], B[i])$ being different for every $i$, which forces $A[i]$ or $B[i]$ to be at least $\sqrt{N}$ for some $i$. Here are both values for the sequence above.

Only $A$ and $B$ were kept, and the original sequence $X$ was forgotten. Given $A[i]$ and $B[i]$, reconstruct $X$.

$X$ is the numbers $1$ through $N$ in some order. If several sequences fit, print the lexicographically smallest one. That means $X[0]$ is as small as possible, and if several candidates remain then $X[1]$ is as small as possible, and so on.

The first line contains the number of test cases, $T$. $T$ test cases follow, each on three lines.

The first line of a test case contains one integer $N$. The second line contains $N$ positive integers separated by spaces, which are $A[0], A[1], \dots, A[N-1]$. The third line contains $B[0], B[1], \dots, B[N-1]$ in the same format.

Limits

• $1 \le T \le 30$
• $1 \le N \le 2000$
• Every test case admits at least one valid $X$.

For each test case, print one line containing Case #x: followed by $X[0], X[1], \dots, X[N-1]$ in order, separated by spaces. Here $x$ is the test case number starting from 1.