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 翻译