bzoj#P4217. Log set

Log set

题目描述

定义一个子集的和为该子集中所有数的和,特别的,定义空集的和为 00

已知一个非空多重整数集合 SS 以及其每个子集的和,构造出原集合 SS,如果有多个可能的 SS,那么输出将 SS 内所有元素排序后,字典序最小的一个。数据保证有解。

输入格式

本题有多组数据

第一行有一个正整数 TT,表示数据组数。

每组数据第一行有一个正整数 nn,接下来两行,第一行 nn 个整数 SiS_i,第二行 nn 个整数 PiP_i,每个数对 (Si,Pi)(S_i,P_i) 表示和为 SiS_i 的子集有 PiP_i 个。

输出格式

对每组数据输出一行 Case #数据编号:,接着按升序输出 SS 中的数,可参考样例输出。

样例

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

样例说明

对第三组数据,多重集 -1 -1 2 同样可能,但是 -2 1 1 的字典序更小,所以应输出 -2 1 1

数据规模与约定

对于 100%100\% 的数据:SS 的大小不超过 6060n104n\le 10^4T100T\le 100Si1010|S_i|\le 10^{10}Pi1P_i\ge 1