Monocarp 玩电脑游戏(又来了!)。该游戏具有独特的交易机制。
要与某个角色进行交易,Monocarp 必须选择他拥有的一件物品,并将其换成另一个角色拥有的某些物品。每个商品都有一个整数价格。如果 Monocarp 选择的物品价格为 $$$x$$$,那么他可以用它交换任何价格不大于 $$$x+k$$$ 的物品(只能是一件物品)。
Monocarp 最初拥有 $$$n$$$ 物品,他拥有的第 $$$i$$$ 物品的价格为 $$$a_i$$$。正在交易的角色 Monocarp 有 $$$m$$$ 物品,他们拥有的第 $$$i$$$ 物品的价格是 $$$b_i$$$。 Monocarp 可以与该角色进行任意多次交易(甚至可能为零次),每次根据上述限制将他的一件物品与其他角色的一件物品交换。请注意,如果 Monocarp 在交换过程中获得了一些物品,他可以用它换取另一件物品(因为现在该物品属于他),反之亦然:如果 Monocarp 用他的一件物品换取另一件物品,他可以通过用某件物品换回他的物品。
您必须回答 $$$q$$$ 查询。每个查询由一个整数组成,即 $$$k$$$ 的值,并要求您计算 Monocarp 在一系列交易后可以拥有的物品的最大可能总成本,假设他可以在每次交易期间将成本为 $$$x$$$ 的物品换成成本不大于 $$$x+k$$$ 的物品。请注意,查询是独立的:交易实际上并未发生,Monocarp 只想计算他可以获得的最大总成本。
输入
第一行包含三个整数 $$$n$$$、$$$m$$$ 和 $$$q$$$ ($$$1 \le n, m, q \le 2 \cdot 10^5$$$)。
第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — Monocarp 拥有的物品的价格。
第三行包含 $$$m$$$ 整数 $$$b_1, b_2, \dots, b_m$$$ ($$$1 \le b_i \le 10^9$$$) — 另一个角色拥有的物品的价格。
第四行包含 $$$q$$$ 整数,其中第 $$$i$$$ 整数是第 $$$i$$$ 查询的 $$$k$$$ 的值 ($$$0 \le k \le 10^9$$$)。
输出
对于每个查询,打印一个整数 - 在给定查询中 $$$k$$$ 的值的情况下,Monocarp 在一系列交易之后可以拥有的最大可能的物品总成本。
示例
输入 #1
3 4 5 10 30 15 12 31 14 18 0 1 2 3 4
输出 #1
55 56 60 64 64