Somewhere in the sky, KM kingdom built `n` floating islands by their highly developed technology.
The islands are numbered from 1 to `n`.

The king of the country, Kita_masa, can choose any non-negative real number as the altitude for each island, as long as the sum of the altitudes is greater than or equals to `H`.
For floating the island `i` to the altitude `h_i`, it costs `b_i h_i`.
Besides, it costs `|h_i - h_j|c_{i,j}` for each pair of islands `i` and `j` since there are communications between these islands.

Recently, energy prices are rising, so the king, Kita_masa, wants to minimize the sum of the costs. The king ordered you, a court programmer, to write a program that finds the altitudes of the floating islands that minimize the cost.

The input contains several test cases.
Each test case starts with a line containing two integers `n` (`1 \leq n \leq 100`) and `H` (`0\leq H \leq 1,000`), separated by a single space.
The next line contains `n` integers `b_1`, `b_2`,..., `b_n` (`0\leq b_i \leq 1,000`).
Each of the next `n` lines contains `n` integers `c_{i,j}` (`0 \leq c_{i,j} \leq 1,000`).
You may assume `c_{i, i} = 0` and `c_{i, j} = c_{j, i}`.

The last test case is followed by a line containing two zeros.

For each test case, print its case number.
Then print a line containing a space-separated list of the altitudes of the islands that minimizes the sum of the costs.
If there are several possible solutions, print any of them.
Your answer will be accepted if the altitude of each island is non-negative, sum of the altitudes is greater than `(1-10^{-9})H`, and the cost calculated from your answer has an absolute or relative error less than `10^{-9}` from the optimal solution.

Follow the format of the sample output.

2 1 1 3 0 1 1 0 3 3 1 2 4 0 2 0 2 0 1 0 1 0 0 0

Case 1: 0.75 0.25 Case 2: 1.5 1.5 0.0

Source: ACM-ICPC Japan Alumni Group Spring Contest 2012
, Tokyo, Japan, 2012-04-15

http://jag-icpc.org/

http://jag-icpc.org/