Description

原题来自：USACO

已知原数列 a₁,a₂,… ,a_n 中的前 1 项，前 2 项，前 3 项， … ，前 n 项的和，以及后 1 项，后 2 项，后 3 项， … ，后 n 项的和，但是所有的数都被打乱了顺序。此外，我们还知道数列中的数存在于集合 S 中。试求原数列。当存在多组可能的数列时，求字典序最小的数列。

Input Format

第 1 行，一个整数 n 。
第 2 行， 2 × n 个整数，注意：数据已被打乱。
第 3 行，一个整数 m ，表示 S 集合的大小。
第 4 行， m 个整数，表示 S 集合中的元素。

Output Format

输出满足条件的最小数列。

5
1 2 5 7 7 9 12 13 14 14
4
1 2 4 5

1 1 5 2 5

Hint

对于 100% 的数据， 1 ≤ n ≤ 1000 ,1≤ m≤ 500 ，且 S ∈ { 1,2,…,500 } 。

样例解释

从左往右求和	从右往左求和
1=1 \phantom{0}1=1\phantom{+1+5+2+5}	5=                   5\phantom{0}5=\phantom{1+1+5+2+}5
2=1+1\phantom{0}2=1+1\phantom{+5+2+5}	7=   2+5\phantom{0}7=\phantom{1+1+5+}2+5
7=1+1+5\phantom{0}7=1+1+5\phantom{+2+5}	12=  5+5+512=\phantom{1+1+}5+2+5
9=1+1+5+2\phantom{0}9=1+1+5+2\phantom{+5}	13=1+5+2+513=\phantom{1+}1+5+2+5
14=1+1+5+2+5

Source

一本通 第三章 深搜的剪枝技巧