問題文

今日、KYOPRO 国では総選挙が行われました。N 個の党が立候補し、i 番目の党は A_i 票を獲得しました。比例代表制にしたがって K 議席を配分するとき、各党は何議席を獲得しますか。

ただし比例代表制では、以下の表のように「票数÷議席数」の大きい方から議席を割り当てていきます（ドント方式といいます）。

制約

• 2 \leq N \leq 100000
• 1 \leq K \leq 10^9
• 1 \leq A_i
• A_1 + A_2 + \cdots + A_N \leq 10^9
• ボーダーとなる「票数÷議席数」の値は 1 を超え 10^9 未満である
• ボーダーとなる「票数÷議席数」と、次点の「票数÷議席数」の相対誤差は 10^{-6} を超える
• 入力はすべて整数

入力例 1

4 10
1000000 700000 300000 180000

出力例 1

5 3 1 1

問題文の図に書かれている通りです。

入力例 2

2 3
6000 3000

出力例 2

2 1

この入力は制約を満たしますが、もし A = [6000, 3000] かつ K=2 である場合はボーダーが同点となるため、制約を満たさないことに注意してください（このような入力は絶対に与えられません）。

入力例 3

15 50
18256245 7845995 6771945 6181431 3618432 3159625 2319156 1768385 1258501 1253872 193724 148020 109045 77861 65107

出力例 3

18 8 7 6 3 3 2 1 1 1 0 0 0 0 0

第 26 回参議院通常選挙のデータです。

入力例 4

2 1
900000000 100000000

出力例 4

1 0