{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":" \n \u003cp\u003e\u003cem\u003e\"K-Dimensional Foil\" is a dimensional weapon. Its function is quite easy: It can ascend a region in 3D space to K (K≥3) dimension. One can use it to give the enemy unexpected attack. It was called \"The Ultimate Weapon\".\u003cbr\u003e\u003c/em\u003e\u003c/p\u003e \n \u003cp style\u003d\"text-align:right;\"\u003e\u003cem\u003e--\"Remembrance of Mars\u0027s Past\"\u003c/em\u003e\u003c/p\u003e \n \u003cp\u003eYou are the chief technology officer in the space fleet, and your fleet was just suffered from the attack of the K-Dimensional Foil. The good news was that you have found the key parameter \u003cvar\u003eK\u003c/var\u003e, the dimension of the space. But staying in high dimensional space is very dangerous, you must destroy the K-Dimensional Foil as fast as possible.\u003c/p\u003e \n \u003cp\u003eYou have \u003cvar\u003en\u003c/var\u003e spaceships, spaceship \u003cvar\u003ei\u003c/var\u003e locates at \u003cvar\u003es\u003csub\u003ei\u003c/sub\u003e \u003d (s\u003csub\u003ei,1\u003c/sub\u003e, …, s\u003csub\u003ei,K\u003c/sub\u003e)\u003c/var\u003e, and the K-Dimensional \u0026nbsp;Foil is a 1-norm ball with center \u003cvar\u003ec \u003d (c\u003csub\u003e1\u003c/sub\u003e, …, c\u003csub\u003eK\u003c/sub\u003e)\u003c/var\u003e and radius \u003cvar\u003er\u003c/var\u003e, a 1-norm ball with center \u003cvar\u003ec\u003c/var\u003e and radius \u003cvar\u003er\u003c/var\u003e is a point set defined as\u003cbr\u003e\u003cvar\u003e{x | \u0026nbsp;d(x, c) \u0026nbsp;≤ r}, d(x, c) \u003d∑| x\u003csub\u003ei\u003c/sub\u003e - c\u003csub\u003ei\u003c/sub\u003e |\u003c/var\u003e\u003c/p\u003e \n \u003cp\u003eIn the formula above, the coordinate of point \u003cvar\u003ex\u003c/var\u003e is \u003cvar\u003e(x\u003csub\u003e1\u003c/sub\u003e, x\u003csub\u003e2\u003c/sub\u003e … x\u003csub\u003eK\u003c/sub\u003e)\u003c/var\u003e\u003c/p\u003e \n \u003cp\u003eYour spaceships will fire laser cannon to destroy the K-Dimensional Foil. The energy decay is very quick with the increase of the distance in the high dimensional space, so for every spaceship, you want to find the closest point (in Euclidean distance) on the K-Dimensional Foil. It\u0027s guaranteed that no spaceship is in the K-Dimensional Foil initially.\u003c/p\u003e \n "}},{"title":"Input","value":{"format":"HTML","content":" \n \u003cp\u003eThe first line of the input is an integer \u003cvar\u003eT\u003c/var\u003e (\u003cvar\u003eT\u003c/var\u003e ≤ 100), the number of the test cases.\u003c/p\u003e \n \u003cp\u003eFor each test case, the first line contains two integer \u003cvar\u003en\u003c/var\u003e, \u003cvar\u003eK\u003c/var\u003e (1 ≤ n ≤ 50, 1 ≤ K ≤ 100), the number of spaceship in your fleet and the dimension of the space.\u003c/p\u003e \n \u003cp\u003eThen one line contains an integer r (1 ≤ r ≤ 10\u003csup\u003e4\u003c/sup\u003e ), the radius of the K-Dimensional Foil.\u003c/p\u003e \n \u003cp\u003eThen one line contains K integers c\u003csub\u003e1\u003c/sub\u003e, … c\u003csub\u003eK\u003c/sub\u003e, meaning the coordinate of the center of the K-Dimensional Foil.\u003c/p\u003e \n \u003cp\u003eThen \u003cvar\u003en\u003c/var\u003e lines follow. Each line contains \u003cvar\u003eK\u003c/var\u003e integers \u003cvar\u003es\u003csub\u003ei,1\u003c/sub\u003e, …, s\u003csub\u003ei,K\u003c/sub\u003e\u003c/var\u003e, meaning the coordinate of a spaceship.\u003c/p\u003e \n \u003cp\u003eAll the absolute values of the coordinate are smaller than 10\u003csup\u003e4\u003c/sup\u003e.\u003c/p\u003e \n "}},{"title":"Output","value":{"format":"HTML","content":" \n \u003cp\u003eFor each test case, output \u003cvar\u003en\u003c/var\u003e lines. The \u003cvar\u003ei\u003c/var\u003e\u003csup\u003eth\u003c/sup\u003e line contains \u003cvar\u003eK\u003c/var\u003e numbers representing the coordinate of the closest point on the K-Dimensional Foil to the \u003cvar\u003ei\u003c/var\u003e\u003csup\u003eth\u003c/sup\u003e spaceship. The absolute error between your output and the answer should be less than 10\u003csup\u003e-4\u003cbr\u003e\u003c/sup\u003e\u003c/p\u003e \n "}},{"title":"Sample Input","value":{"format":"HTML","content":" \n \u003cpre\u003e1\r\n2 2\r\n1\r\n0 0\r\n1 1\r\n1 3\u003c/pre\u003e \n "}},{"title":"Sample Output","value":{"format":"HTML","content":" \n \u003cpre\u003e0.50 0.50\r\n0.00 1.00\u003c/pre\u003e \n "}},{"title":"Hint","value":{"format":"HTML","content":" \n \u003cp\u003eThe K-Dimensional Foil in the sample was a square with vertex: (1,0), (0,1), (-1,0), (0,-1)\u003c/p\u003e \n \u003cp\u003eThis problem is special judged.\u003cbr\u003e\u003c/p\u003e \n \u003c/div\u003e \n "}}]}