Description

给定一个数列 $X$，其内容为 $(1, 2, \ldots, N)$。一个递增子序列是指这些数字中按递增顺序出现的某个子集；递减子序列则是按递减顺序出现的子集。例如，$(5, 7, 8)$ 是 $(4, 5, 3, 7, 6, 2, 8, 1)$ 的一个递增子序列。

大约 80 年前，两位数学家 Paul Erdős 和 George Szekeres 证明了一个著名结论：$X$ 一定存在长度至少为 $\sqrt{N}$ 的递增子序列，或长度至少为 $\sqrt{N}$ 的递减子序列。例如，$(4, 5, 3, 7, 6, 2, 8, 1)$ 有一个长度为 $4$ 的递减子序列 $(5, 3, 2, 1)$。

我正在教授组合数学课程，想通过实例“证明”这个定理。对于序列中每个 $X[i]$，我会计算两个值：

• $A[i]$：包含 $X[i]$ 且以 $X[i]$ 为最大值的最长递增子序列的长度。
• $B[i]$：包含 $X[i]$ 且以 $X[i]$ 为最大值的最长递减子序列的长度。

我的证明关键在于，对于每个 $i$，$(A[i], B[i])$ 这对值都是不同的，这就意味着对于某个 $i$，$A[i]$ 或 $B[i]$ 至少有一个不小于 $\sqrt{N}$。对于上面的序列，所有 $A[i]$ 和 $B[i]$ 的值如下表：

我曾经设计了一个很有趣的数列来演示这个事实，并且为每个 $i$ 计算了 $A[i]$ 和 $B[i]$，但后来却忘记了原始的数列是什么。现在，给定 $A[i]$ 和 $B[i]$，你能帮我还原出 $X$ 吗？

$X$ 应该是 $(1, 2, \ldots, N)$ 的某种排列。如果有多种可能的数列，请输出字典序最小的那一个。也就是说，$X[0]$ 应尽量小，如果还有多种方案，则 $X[1]$ 尽量小，依此类推。

Input Format

输入的第一行为测试用例数 $T$。接下来有 $T$ 个测试用例，每个测试用例包含三行。

每个测试用例的第一行为一个整数 $N$。第二行为 $N$ 个正整数，依次为 $A[0], A[1], \dots, A[N-1]$。第三行为 $N$ 个正整数，依次为 $B[0], B[1], \dots, B[N-1]$。

Output Format

对于每个测试用例，输出一行 "Case #x: "，后接 $X[0], X[1], \dots, X[N-1]$，用空格分隔。

2
1
1
1
8
1 2 1 3 3 1 4 1
4 4 3 4 3 2 2 1

Case #1: 1
Case #2: 4 5 3 7 6 2 8 1

Hint

限制条件

• $1 \leq T \leq 30$
• 保证至少存在一个可行解

小数据集（9 分，测试集 1 - 可见）

• $1 \leq N \leq 20$

大数据集（15 分，测试集 2 - 隐藏）

• $1 \leq N \leq 2000$

翻译由 ChatGPT-4.1 完成。