AT_abc123_d [ABC123D] Cake 123

[problemUrl]: https://atcoder.jp/contests/abc123/tasks/abc123_d 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 $ の形のキャンドルがついたケーキを $ 1 $ つずつ買うことにしました。 そのようにケーキを買う方法は $ X\ \times\ Y\ \times\ Z $ 通りあります。 これらの選び方を $ 3 $ つのケーキの美味しさの合計が大きい順に並べたとき、$ 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 $

$ i $ 行目に、問題文中の $ i $ 番目の値を出力せよ。

### 制約 - $ 1\ \leq\ X\ \leq\ 1\ 000 $ - $ 1\ \leq\ Y\ \leq\ 1\ 000 $ - $ 1\ \leq\ Z\ \leq\ 1\ 000 $ - $ 1\ \leq\ K\ \leq\ \min(3\ 000,\ 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 $ - 入力中の値はすべて整数である。 ### Sample Explanation 1 $ 3 $ つのケーキの選び方は $ 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 $ ### Sample Explanation 2 美味しさの合計が同じになる組み合わせが複数ある可能性もあります。例えば、このテストケースで $ (A_1,\ B_3,\ C_3) $ を選ぶときと $ (A_3,\ B_3,\ C_1) $ を選ぶときはともに、美味しさの合計が $ 301 $ となります。 しかし、これらは異なる選び方であるため、出力には $ 301 $ が $ 2 $ 回出現します。 ### Sample Explanation 3 入力・出力は $ 32 $ ビット整数に収まらない可能性があることに注意してください。