There are several points on the plane named beauty points. Given a point A, its ugliness is defined as |AB|+|AC|, where B and C are two beauty points nearest to A.
Your task is: given beauty points, find the most beautiful point, i.e., the point having least ugliness. Note: the most beautiful point doesn't have to be a beauty point.
The first line of the input contains the number of the test cases, which is at most 10. The descriptions of the test cases follow. The first line of a test case descriptions contains an integer N (2 ≤ N ≤ 10000), which is the number of beauty points. Each of the next N lines contains two integers X and Y separated by a space (-10000 ≤ X, Y ≤ 10000) being the coordinates of a beauty point. No two beauty points in a test case description have the same coordinates. The test cases are separated by blank lines.
For each test case in the input, output the coordinates of any most beautiful point separated by a space, with at least three digits after the decimal point. Print a blank line between test cases.
| Input | Output |
2 4 0 0 0 1 1 1 1 0 4 -1 -1 0 0 1 0 2 1 | 0.500 0.000 0.500 0.000 |