問題文

アイドルグループ ATC48 にて、N 人のアイドルたちに人気投票が行われ、各アイドルに a_1, a_2, \ldots, a_N の投票が集まりました。

各アイドルには得票数に応じた賞金を渡します。事前に X 円 (X は正の整数) の賞金が用意されていて、なるべくアイドル i には a_i に比例する賞金を渡したいです。しかし、A = a_1 + a_2 + \dots + a_N として X \times \frac{a_i}{A} が整数値になるとは限りません。そこで各アイドルに渡す賞金額 x_1, x_2, \ldots, x_N を以下の条件を満たす 0 以上の整数値となるように決めることにしました:

• x_1 + x_2 + \ldots + x_N = X
• |\frac{x_1}{a_1} - \frac{X}{A}| + |\frac{x_2}{a_2} - \frac{X}{A}| + \ldots + |\frac{x_N}{a_N} - \frac{X}{A}| が最小値をとる。

各アイドルの賞金額 x_1, x_2, \ldots, x_N を出力するプログラムを作ってください。複数通り考えられる場合には、(x_1, x_2, \ldots, x_N) の辞書順が最小のものを出力してください。

制約

• 1 \le N \le 10^5
• 1 \le X \le 10^9
• 1 \le a_i \le 100
• 与えられる入力はすべて整数です。

入力例 1

4 100
3 4 5 8

出力例 1

15
20
25
40

この場合はちょうど比例配分することができます。

入力例 2

2 100
3 4

出力例 2

43
57

このとき |\frac{43}{3} - \frac{100}{7}| + |\frac{57}{4} - \frac{100}{7}| = 0.083333… となります。

入力例 3

6 1000
7 6 1 3 4 1

出力例 3

318
273
45
136
182
46

複数通り考えられる場合は、辞書順最小のものを出力します。