题目描述

小 C 带着 $n$ 件物品来到集市，第 $i$ 件物品的市场价为 $p_i$。集市上目前流通着 $m$ 件物品，第 $i$ 件物品的市场价为 $q_i$。

集市采取“物物交换”的方式，小 C 可以将他手中的一件物品与集市上某一件物品进行交易。市场上有一个宽容度 $k$，如果交易的两个物品的市场价分别为 $x$ 和 $y$，那么当 $|x - y| \le k$ 时，这笔交易就可以达成（注意交易后，集市上的物品变为小 C 手中的物品，小 C 手中的物品变为集市上的物品，可以进行连续多次交易）。

小 C 希望通过交易来提高他手中物品的总市场价。但是，他并不清楚集市的宽容度 $k$ 是多少。所以他会进行 $t$ 次假设，每次假设一个不同的宽容度 $k_i$，并希望你能帮他计算出在每次假设的宽容度下，他能通过交易得到的最大市场价之和。

输入格式

第一行包含三个正整数 $n, m$ 和 $t$ —— 依次表示小 C 带的物品数、集市流通的物品数以及小 C 假设的次数。

第二行包含 $n$ 个正整数 $p_1, p_2, \dots, p_n$ —— 依次表示小 C 手上物品的市场价。

第三行包含 $m$ 个正整数 $q_1, q_2, \dots, q_m$ —— 依次表示集市中流通的物品的市场价。

第四行包含 $t$ 个非负整数 $k_1, k_2, \dots, k_t$ —— 依次表示小 C 每次假设的宽容度。

输出格式

输出一行，包含 $t$ 个整数，依次表示在每次假设的宽容度下，小 C 能通过交易得到的最大的市场价之和。相邻整数之间用一个空格隔开。

样例输入 1

3 4 4
10 25 5
7 26 9 13
3 2 1 0

样例输出 1

49 45 41 40

说明

样例解释

在下方解释中，加粗的数字表示初始为小 C 的物品对应的市场价，未加粗的表示集市流通的物品对应的市场价。

• 当 $k = 3$ 时，先通过第一个物品交易 10 $\rightarrow 13$；再通过第三个物品交易 5 $\rightarrow 7 \rightarrow 9 \rightarrow$ 10；最后交易第二个物品 25 $\rightarrow 26$。最终总市场价为 $13 + 26 +$ 10 $= 49$。
• 当 $k = 2$ 时，通过交易第三个物品 5 $\rightarrow 7 \rightarrow 9$；再通过交易第二个物品 25 $\rightarrow 26$。最终总市场价为 10 $+ 26 + 9 = 45$。
• 当 $k = 1$ 时，只能交易第二个物品 25 $\rightarrow 26$。最终总市场价为 10 $+ 26 +$ 5 $= 41$。
• 当 $k = 0$ 时，无法达成任何交易。最终总市场价为 10 $+$ 25 $+$ 5 $= 40$。

其它样例说明

• 样例 $2$：见选手附加文件目录下的 market/market2.in 和 market/market2.ans。该组数据满足测试点 $5 \sim 6$ 的条件：$n, m \le 100$，$t = 1$。
• 样例 $3$：见选手附加文件目录下的 market/market3.in 和 market/market3.ans。该组数据满足测试点 $7 \sim 8$ 的条件：$n, m, t \le 100$。
• 样例 $4$：见选手附加文件目录下的 market/market4.in 和 market/market4.ans。该组数据满足测试点 $11 \sim 14$ 的条件：$n, m, t \le 5000$。

数据范围

对于所有数据，保证 $1 \le n, m, t \le 3 \times 10^5$，$0 \le k_i \le 10^9$，$1 \le p_i, q_i \le 10^9$。 保证所有的输入数值均为整数。

各测试点的附加限制如下表所示：

点击下载大样例