{"raw_statement":[{"iden":"problem statement","content":"The Patisserie AtCoder sells cakes with number-shaped candles. There are $X$, $Y$ and $Z$ kinds of cakes with $1$\\-shaped, $2$\\-shaped and $3$\\-shaped candles, respectively. Each cake has an integer value called _deliciousness_, as follows:\n\n*   The deliciousness of the cakes with $1$\\-shaped candles are $A_1, A_2, ..., A_X$.\n*   The deliciousness of the cakes with $2$\\-shaped candles are $B_1, B_2, ..., B_Y$.\n*   The deliciousness of the cakes with $3$\\-shaped candles are $C_1, C_2, ..., C_Z$.\n\nTakahashi decides to buy three cakes, one for each of the three shapes of the candles, to celebrate ABC 123.  \nThere are $X \\times Y \\times Z$ such ways to choose three cakes.  \nWe will arrange these $X \\times Y \\times Z$ ways in descending order of the sum of the deliciousness of the cakes.  \nPrint the sums of the deliciousness of the cakes for the first, second, $...$, $K$\\-th ways in this list."},{"iden":"constraints","content":"*   $1 \\leq X \\leq 1 \\ 000$\n*   $1 \\leq Y \\leq 1 \\ 000$\n*   $1 \\leq Z \\leq 1 \\ 000$\n*   $1 \\leq K \\leq \\min(3 \\ 000, X \\times Y \\times Z)$\n*   $1 \\leq A_i \\leq 10 \\ 000 \\ 000 \\ 000$\n*   $1 \\leq B_i \\leq 10 \\ 000 \\ 000 \\ 000$\n*   $1 \\leq C_i \\leq 10 \\ 000 \\ 000 \\ 000$\n*   All values in input are integers."},{"iden":"input","content":"Input is given from Standard Input in the following format:\n\n$X$ $Y$ $Z$ $K$\n$A_1 \\ A_2 \\ A_3 \\ ... \\ A_X$\n$B_1 \\ B_2 \\ B_3 \\ ... \\ B_Y$\n$C_1 \\ C_2 \\ C_3 \\ ... \\ C_Z$"},{"iden":"sample input 1","content":"2 2 2 8\n4 6\n1 5\n3 8"},{"iden":"sample output 1","content":"19\n17\n15\n14\n13\n12\n10\n8\n\nThere are $2 \\times 2 \\times 2 = 8$ ways to choose three cakes, as shown below in descending order of the sum of the deliciousness of the cakes:\n\n*   $(A_2, B_2, C_2)$: $6 + 5 + 8 = 19$\n*   $(A_1, B_2, C_2)$: $4 + 5 + 8 = 17$\n*   $(A_2, B_1, C_2)$: $6 + 1 + 8 = 15$\n*   $(A_2, B_2, C_1)$: $6 + 5 + 3 = 14$\n*   $(A_1, B_1, C_2)$: $4 + 1 + 8 = 13$\n*   $(A_1, B_2, C_1)$: $4 + 5 + 3 = 12$\n*   $(A_2, B_1, C_1)$: $6 + 1 + 3 = 10$\n*   $(A_1, B_1, C_1)$: $4 + 1 + 3 = 8$"},{"iden":"sample input 2","content":"3 3 3 5\n1 10 100\n2 20 200\n1 10 100"},{"iden":"sample output 2","content":"400\n310\n310\n301\n301\n\nThere may be multiple combinations of cakes with the same sum of the deliciousness. For example, in this test case, the sum of $A_1, B_3, C_3$ and the sum of $A_3, B_3, C_1$ are both $301$. However, they are different ways of choosing cakes, so $301$ occurs twice in the output."},{"iden":"sample input 3","content":"10 10 10 20\n7467038376 5724769290 292794712 2843504496 3381970101 8402252870 249131806 6310293640 6690322794 6082257488\n1873977926 2576529623 1144842195 1379118507 6003234687 4925540914 3902539811 3326692703 484657758 2877436338\n4975681328 8974383988 2882263257 7690203955 514305523 6679823484 4263279310 585966808 3752282379 620585736"},{"iden":"sample output 3","content":"23379871545\n22444657051\n22302177772\n22095691512\n21667941469\n21366963278\n21287912315\n21279176669\n21160477018\n21085311041\n21059876163\n21017997739\n20703329561\n20702387965\n20590247696\n20383761436\n20343962175\n20254073196\n20210218542\n20150096547\n\nNote that the input or output may not fit into a $32$\\-bit integer type."}],"translated_statement":null,"sample_group":[],"show_order":["default"],"formal_statement":null,"simple_statement":null,"has_page_source":true}