AT_abc123_d.[ABC123D] Cake 123

AtCoder 洋菓子店出售带有数字形状蜡烛的蛋糕。
这里有分别带有 $1$、$2$、$3$ 形状蜡烛的蛋糕，各有 $X$ 种、$Y$ 种、$Z$ 种。
每种蛋糕都被分配了一个“美味度”，其整数值如下：

• 带有 $1$ 形状蜡烛的蛋糕的美味度分别为 $A_1,\ A_2,\ ...,\ A_X$。
• 带有 $2$ 形状蜡烛的蛋糕的美味度分别为 $B_1,\ B_2,\ ...,\ B_Y$。
• 带有 $3$ 形状蜡烛的蛋糕的美味度分别为 $C_1,\ C_2,\ ...,\ C_Z$。

高桥君为了纪念 ABC 123，决定各买一块带有 $1$、$2$、$3$ 形状蜡烛的蛋糕。
这样的选法共有 $X \times Y \times Z$ 种。

请将所有选法按三块蛋糕美味度总和从大到小排序，输出第 $1,2,...,K$ 个选法对应的美味度总和。

输入通过标准输入给出，格式如下：

$X$ $Y$ $Z$ $K$
$A_1\ A_2\ A_3\ ...\ A_X$
$B_1\ B_2\ B_3\ ...\ B_Y$
$C_1\ C_2\ C_3\ ...\ C_Z$

请输出 $K$ 行，第 $i$ 行输出第 $i$ 大的美味度总和。

约束条件

• $1 \leq X \leq 1000$
• $1 \leq Y \leq 1000$
• $1 \leq Z \leq 1000$
• $1 \leq K \leq \min(3000, X \times Y \times Z)$
• $1 \leq A_i \leq 10\,000\,000\,000$
• $1 \leq B_i \leq 10\,000\,000\,000$
• $1 \leq C_i \leq 10\,000\,000\,000$
• 输入中的所有数均为整数。

样例解释 1

三块蛋糕的选法共有 $2 \times 2 \times 2 = 8$ 种，将它们按美味度总和从大到小排序如下：

• $(A_2, B_2, C_2)$: $6 + 5 + 8 = 19$
• $(A_1, B_2, C_2)$: $4 + 5 + 8 = 17$
• $(A_2, B_1, C_2)$: $6 + 1 + 8 = 15$
• $(A_2, B_2, C_1)$: $6 + 5 + 3 = 14$
• $(A_1, B_1, C_2)$: $4 + 1 + 8 = 13$
• $(A_1, B_2, C_1)$: $4 + 5 + 3 = 12$
• $(A_2, B_1, C_1)$: $6 + 1 + 3 = 10$
• $(A_1, B_1, C_1)$: $4 + 1 + 3 = 8$

样例解释 2

也可能存在多种选法的美味度总和相同。例如，在本测试用例中，选择 $(A_1, B_3, C_3)$ 和 $(A_3, B_3, C_1)$ 时，美味度总和均为 $301$。但这属于不同的选法，因此输出中 $301$ 会出现两次。

样例解释 3

请注意，输入输出的数值可能超出 $32$ 位整数范围。

由 ChatGPT 4.1 翻译