题目描述

原题来自：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 \subseteq \{ 1, 2, \cdots, 500 \}$。