#10249. 「一本通 1.3 例 5」weight

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: luyanaa

题目描述

原题来自:USACO

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

输入格式

1 行,一个整数 n
2 行, 2 \times n 个整数,注意:数据已被打乱。
3 行,一个整数 m ,表示 S 集合的大小。
4 行, m 个整数,表示 S 集合中的元素。

输出格式

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

样例

样例输入

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

样例输出

1 1 5 2 5

数据范围与提示

数据范围

对于 100\% 的数据, 1 \le n \le 1000 ,1\le m\le 500 ,且 S \in \{ 1,2,\cdots,500 \}

样例解释

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