AT_abc440_e [ABC440E] Cookies

$ N $ 種類のクッキーがそれぞれ $ 10^{100} $ 枚あります。 $ i $ 種類目のクッキーの $ 1 $ 枚あたりの美味しさは $ A_i $ です。 これらのクッキーから合計で $ K $ 枚を選びます。クッキーの選び方は、選んだクッキーの種類の多重集合が一致するときかつその時に限り同じとみなします。 全ての選び方 $ \binom{N+K-1}{K} $ 通りそれぞれについて、選んだクッキーの美味しさの和を考えます。これらを大きな値から順に重複を込めて $ S_1,S_2,\dots $ とするとき、 $ S_1,\dots,S_X $ を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ K $ $ X $ $ A_1 $ $ \dots $ $ A_N $

$ K $ 枚選んだクッキーの美味しさの和として考えられる値を、大きなものから順に重複を込めて $ S_1,S_2,\dots $ とするとき、 $ S_1,\dots,S_X $ をこの順に改行区切りで出力せよ。

### Sample Explanation 1 クッキーを $ 4 $ 枚選ぶ方法は、「 $ 1 $ 種類目を $ k $ 枚、 $ 2 $ 種類目を $ 4-k $ 枚」 $ (0\leq k \leq 4) $ の $ 5 $ 通りあり、選んだクッキーの美味しさの和はそれぞれ $ 80,70,60,50,40 $ となります。 ### Sample Explanation 2 異なるクッキーの選び方で美味しさの和が同じになることもあります。 ### Constraints - $ 1\leq N \leq 50 $ - $ 1 \leq K \leq 10^5 $ - $ 1 \leq X \leq \min\left(10^5, \binom{N+K-1}{K}\right) $ - $ -10^9 \leq A_i \leq 10^9 $ - 入力は全て整数