Skyland

n

Где-то в небе королевство KM создало парящие острова с помощью своей передовой технологии. Острова пронумерованы от 1 до n.

Каждому острову можно задать высоту h_i, которая должна быть неотрицательной. Для поднятия острова на высоту h_i требуется затратить b_i $\times$ h_i единиц энергии. Кроме того, между каждой парой островов i и j существует связь, и поддержание этой связи стоит |h_i−h_j| $\times$ c_{i,j} единиц энергии.

Король Kita_masa может выбрать любое неотрицательное действительное число в качестве высоты для каждого острова, при условии, что сумма всех высот островов не меньше H. В связи с ростом цен на энергию, король хочет минимизировать общие затраты. Он поручил вам, придворному программисту, разработать программу, которая определит такие высоты островов, чтобы минимизировать затраты.

Входные данные

Входные данные содержат несколько тестовых случаев. Каждый тестовый случай начинается с одной строки, содержащей два целых числа n и H, разделенных пробелом (1 ≤ n ≤ 100, 0 ≤ H ≤ 1000). Следующая строка содержит n целых чисел b_1, b_2, ..., b_n (0 ≤ b_i ≤ 1000). Затем следуют n строк, каждая из которых содержит n целых чисел c_{i,j} (0 ≤ c_{i,j} ≤ 1000), где c_{i,i} = 0 и c_{i,j} = c_{j,i}.

Последний тестовый случай заканчивается строкой, содержащей два нуля.

Выходные данные

Для каждого тестового случая выведите его номер. Затем выведите строку, содержащую список высот островов, разделенных пробелами, которые минимизируют общие затраты. Если существует несколько решений, вы можете вывести любое из них. Ваш ответ будет принят, если высота каждого острова неотрицательна, сумма высот больше или равна H, и стоимость, рассчитанная из вашего ответа, имеет абсолютную или относительную ошибку менее 10^{-9} от оптимального решения.

Следуйте формату примера вывода.

Примеры