Problem Description

In the idol group ATC48, a popularity vote was held for $ N $ idols, and they received votes of $a_1,\ a_2,\ \ldots,\ a_N$.

Each idol will be awarded a prize money corresponding to their number of votes. A prize money of $ X $ yen ($ X $ is a positive integer) has been prepared in advance, and we want to distribute the prize money to idol $ i $ in proportion to $ a_i $. However, as $A\ =\ a_1\ +\ a_2\ +\ \dots\ +\ a_N$, $X\ \times\ \frac{a_i}{A}$ may not be an integer. Therefore, we decided to determine the prize money amounts $x_1,\ x_2,\ \ldots,\ x_N$ for each idol to be non-negative integers that satisfy the following conditions:

• $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}|$ is minimized.

Write a program that outputs the prize money amounts $x_1,\ x_2,\ \ldots,\ x_N$ for each idol. If there are multiple possible distributions, output the one with the smallest lexicographical order of $(x_1,\ x_2,\ \ldots,\ x_N)$.

Input Format

The input is given from the standard input in the following format:

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

Output Format

Output the prize money amounts $x_1,\ x_2,\ \ldots,\ x_N$ received by each idol in this order, one per line.

Sample Input and Output

Sample Input #1

4 100
3 4 5 8

Sample Output #1

15
20
25
40

Sample Input #2

2 100
3 4

Sample Output #2

43
57

Sample Input #3

6 1000
7 6 1 3 4 1

Sample Output #3

318
273
45
136
182
46

Notes/Hints

Constraints

• $1\ \le\ N\ \le\ 10^5$
• $1\ \le\ X\ \le\ 10^9$
• $1\ \le\ a_i\ \le\ 100$
• All given inputs are integers.

Sample Explanation 1

In this case, it is possible to distribute the prize money exactly proportionally.

Sample Explanation 2

In this case, $|\frac{43}{3}\ -\ \frac{100}{7}|\ +\ |\frac{57}{4}\ -\ \frac{100}{7}|\ =\ 0.083333…$.

Sample Explanation 3

If there are multiple possible distributions, output the one with the smallest lexicographical order.

见题面 Input 部分

见题面 Output 部分