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

「一本通 1.3 例 5」weight

题目描述

原题来自:USACO

已知原数列 a1,a2,,ana_1,a_2,\cdots,a_n 中的前 11 项,前 22 项,前 33 项, \cdots ,前 nn 项的和,以及后 11 项,后 22 项,后 33 项, \cdots ,后 nn 项的和,但是所有的数都被打乱了顺序。此外,我们还知道数列中的数存在于集合 SS 中。试求原数列。当存在多组可能的数列时,求字典序最小的数列。

输入格式

11 行,一个整数 nn
22 行, 2×n 2 \times n 个整数,注意:数据已被打乱。
33 行,一个整数 mm ,表示 SS 集合的大小。
44 行, mm 个整数,表示 SS 集合中的元素。

输出格式

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

样例

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

数据范围与提示

数据范围

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

样例解释

从左往右求和 从右往左求和
01=1+1+5+2+5\phantom{0}1=1\phantom{+1+5+2+5} 05=1+1+5+2+5\phantom{0}5=\phantom{1+1+5+2+}5
02=1+1+5+2+5\phantom{0}2=1+1\phantom{+5+2+5} 07=1+1+5+2+5\phantom{0}7=\phantom{1+1+5+}2+5
07=1+1+5+2+5\phantom{0}7=1+1+5\phantom{+2+5} 12=1+1+5+2+512=\phantom{1+1+}5+2+5
09=1+1+5+2+5\phantom{0}9=1+1+5+2\phantom{+5} 13=1+1+5+2+513=\phantom{1+}1+5+2+5
14=1+1+5+2+514=1+1+5+2+5