配点 : 800 点
問題文
在偶像团体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
如果有多个选项,则按字典顺序输出最小的一个。