問題文

アイドルグループ 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$
• 与えられる入力はすべて整数です。

入力

入力は以下の形式で標準入力から与えられます。

$N$ $X$ $a_1$ $a_2$ $\\ldots$ $a_N$

出力

各アイドルの受け取る賞金額 $x_1, x_2, \\ldots, x_N$ をこの順に一行ずつ出力してください。

入力例 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

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