{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003ch1\u003e\u003c/h1\u003e\n\n\u003cp\u003e\nSomewhere in the sky, KM kingdom built \u003cvar\u003en\u003c/var\u003e floating islands by their highly developed technology.\nThe islands are numbered from 1 to \u003cvar\u003en\u003c/var\u003e.\n\u003c/p\u003e\n\n\u003cp\u003e\nThe 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 \u003cvar\u003eH\u003c/var\u003e.\nFor floating the island \u003cvar\u003ei\u003c/var\u003e to the altitude \u003cvar\u003eh_i\u003c/var\u003e, it costs \u003cvar\u003eb_i h_i\u003c/var\u003e.\nBesides, it costs \u003cvar\u003e|h_i - h_j|c_{i,j}\u003c/var\u003e for each pair of islands \u003cvar\u003ei\u003c/var\u003e and \u003cvar\u003ej\u003c/var\u003e since there are communications between these islands.\n\u003c/p\u003e\n\n\u003cp\u003e\nRecently, energy prices are rising, so the king, Kita_masa, wants to minimize the sum of the costs.\nThe king ordered you, a court programmer, to write a program that finds the altitudes of the floating islands that minimize the cost.\n\u003c/p\u003e\n\n\u003ch2\u003eInput\u003c/h2\u003e\n\n\u003cp\u003e\nThe input contains several test cases.\nEach test case starts with a line containing two integers \u003cvar\u003en\u003c/var\u003e (\u003cvar\u003e1 \\leq n \\leq 100\u003c/var\u003e) and \u003cvar\u003eH\u003c/var\u003e (\u003cvar\u003e0\\leq H \\leq 1,000\u003c/var\u003e), separated by a single space.\nThe next line contains \u003cvar\u003en\u003c/var\u003e integers \u003cvar\u003eb_1\u003c/var\u003e, \u003cvar\u003eb_2\u003c/var\u003e,..., \u003cvar\u003eb_n\u003c/var\u003e (\u003cvar\u003e0\\leq b_i \\leq 1,000\u003c/var\u003e).\nEach of the next \u003cvar\u003en\u003c/var\u003e lines contains \u003cvar\u003en\u003c/var\u003e integers \u003cvar\u003ec_{i,j}\u003c/var\u003e (\u003cvar\u003e0 \\leq c_{i,j} \\leq 1,000\u003c/var\u003e).\nYou may assume \u003cvar\u003ec_{i, i} \u003d 0\u003c/var\u003e and \u003cvar\u003ec_{i, j} \u003d c_{j, i}\u003c/var\u003e.\n\u003c/p\u003e\n\n\u003cp\u003e\nThe last test case is followed by a line containing two zeros.\n\u003c/p\u003e\n\n\u003ch2\u003eOutput\u003c/h2\u003e\n\n\u003cp\u003e\nFor each test case, print its case number.\nThen print a line containing a space-separated list of the altitudes of the islands that minimizes the sum of the costs.\nIf there are several possible solutions, print any of them.\nYour answer will be accepted if the altitude of each island is non-negative, sum of the altitudes is greater than \u003cvar\u003e(1-10^{-9})H\u003c/var\u003e, and the cost calculated from your answer has an absolute or relative error less than \u003cvar\u003e10^{-9}\u003c/var\u003e from the optimal solution.\n\u003c/p\u003e\n\n\u003cp\u003e\nFollow the format of the sample output.\n\u003c/p\u003e\n\n\u003ch2\u003eSample Input\u003c/h2\u003e\n\n\u003cpre\u003e2 1\n1 3\n0 1\n1 0\n3 3\n1 2 4\n0 2 0\n2 0 1\n0 1 0\n0 0\n\u003c/pre\u003e\n\n\u003ch2\u003eOutput for the Sample Input\u003c/h2\u003e\n\n\u003cpre\u003eCase 1:\n0.75 0.25\nCase 2:\n1.5 1.5 0.0\n\u003c/pre\u003e\n"}}]}