Description

集合 $\mathrm{S}$ 的幂集是 $\mathrm{S}$ 的所有子集（包括空集和 $\mathrm{S}$ 本身）组成的集合。从一个集合得到它的幂集很容易，但在本题中，我们要反过来操作！

我们从一个（元素不一定唯一的）整数集合 $\mathrm{S}$ 出发，求出它的幂集，然后将幂集中的每个元素替换为该子集元素之和，得到一个新集合 $\mathrm{S}^{\prime}$。例如，如果 $\mathrm{S}=\{-1,1\}$，那么 $\mathrm{S}$ 的幂集为 $\{\{\},\{-1\},\{1\},\{-1,1\}\}$，所以 $\mathrm{S}^{\prime}=\{0,-1,1,0\}$。$\mathrm{S}^{\prime}$ 允许包含重复元素，因此如果 $\mathrm{S}$ 有 $\mathrm{N}$ 个元素，则 $\mathrm{S}^{\prime}$ 一定有 $2^{\mathrm{N}}$ 个元素。

给定 $\mathrm{S}^{\prime}$ 中各元素及其出现次数的信息，你能还原出原始集合 $\mathrm{S}$ 吗？保证 $\mathrm{S}$ 存在。如果有多个可能的集合 $\mathrm{S}$ 能生成相同的 $\mathrm{S}^{\prime}$，则保证原始集合 $\mathrm{S}$ 是这些可能集合中“最早”的那个。判断集合 $\mathrm{S}_1$ 是否比集合 $\mathrm{S}_2$ 更早的方法如下：将每个集合按非递减顺序排序，比较第一个不同的位置，若 $\mathrm{S}_1$ 在该位置的元素小于 $\mathrm{S}_2$，则 $\mathrm{S}_1$ 更早。

Input Format

输入的第一行包含测试用例数 $\mathrm{T}$。接下来有 $\mathrm{T}$ 组测试数据。每组测试数据包括一行整数 $\mathrm{P}$，接着两行，每行有 $\mathrm{P}$ 个用空格分隔的整数。第一行为所有出现在 $\mathrm{S}^{\prime}$ 中的不同元素 $\mathrm{E}_1, \mathrm{E}_2, \ldots, \mathrm{E}_{\mathrm{P}}$，按升序排列。第二行为这些元素在 $\mathrm{S}^{\prime}$ 中出现的次数 $\mathrm{F}_1, \mathrm{F}_2, \ldots, \mathrm{F}_{\mathrm{P}}$。也就是说，对于任意 $i$，元素 $\mathrm{E}_i$ 在 $\mathrm{S}^{\prime}$ 中出现 $\mathrm{F}_i$ 次。

Output Format

对于每组测试数据，输出一行，格式为 "Case #x: "，其中 $x$ 为测试用例编号（从 1 开始），后接原始集合 $\mathrm{S}$ 的所有元素，按非递减顺序，用空格分隔。（你需要直接输出 $\mathrm{S}$ 的元素，不需要像 $\mathrm{S}^{\prime}$ 那样输出元素和出现次数两行。）

5
8
0 1 2 3 4 5 6 7
1 1 1 1 1 1 1 1
4
0 1 2 3
1 3 3 1
4
0 1 3 4
4 4 4 4
3
-1 0 1
1 2 1
5
-2 -1 0 1 2
1 2 2 2 1

Case #1: 1 2 4
Case #2: 1 1 1
Case #3: 0 0 1 3
Case #4: -1 1
Case #5: -2 1 1

Hint

样例解释

注意，第 4、5 组样例不在 Small 数据范围内。

第 4 组样例中，$\mathrm{S}=\{-1,1\}$ 是唯一满足条件的集合。（它的子集为 $\{\},\{-1\},\{1\},\{-1,1\}$，这些子集的和分别为 $0, -1, 1, 0$，所以 $\mathrm{S}^{\prime}$ 包含 $-1$ 一次，$0$ 两次，$1$ 一次，正好与输入相符。）

对于第 5 组样例，$\mathrm{S}=\{-1,-1,2\}$ 也能生成相同的 $\mathrm{S}^{\prime}=\{-2,-1,-1,0,0,1,1,2\}$，但 $\mathrm{S}=\{-2,1,1\}$ 比 $\{-1,-1,2\}$ 更早，因为在第一个不同的位置，$-2<-1$。因此 $-1\ -1\ 2$ 不是可接受答案。$1\ -2\ 1$ 也不被接受，虽然它是正确集合，但元素未按非递减顺序输出。

数据范围

• $1 \leq \mathrm{T} \leq 100$。
• $1 \leq \mathrm{P} \leq 10000$。
• $\mathrm{F}_i \geq 1$。

Small 数据集

• 时间限制：5 秒。
• $\mathrm{S}$ 的元素个数在 1 到 20 之间。
• $0 \leq$ 每个 $\mathrm{E}_i \leq 10^8$。

Large 数据集

• 时间限制：10 秒。
• $\mathrm{S}$ 的元素个数在 1 到 60 之间。
• $-10^{10} \leq$ 每个 $\mathrm{E}_i \leq 10^{10}$。

由 ChatGPT 4.1 翻译