Geometry Problem

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 262144/262144 K (Java/Others)

Description

Alice is interesting in computation geometry problem recently. She found a interesting problem and solved it easily. Now she will give this problem to you :

You are given $N$ distinct points $(X_i,Y_i)$ on the two-dimensional plane. Your task is to find a point $P$ and a real number $R$, such that for at least $\lceil \frac{N}{2} \rceil$ given points, their distance to point $P$ is equal to $R$.

Input

The first line is the number of test cases.

For each test case, the first line contains one positive number $N(1 \leq N \leq 10^5)$.

The following $N$ lines describe the points. Each line contains two real numbers $X_i$ and $Y_i$ $(0 \leq |X_i|, |Y_i| \leq 10^3)$ indicating one give point. It's guaranteed that $N$ points are distinct.

Output

For each test case, output a single line with three real numbers $X_P, Y_P, R$, where $(X_P,Y_P)$ is the coordinate of required point $P$. Three real numbers you output should satisfy $0 \leq |X_P|, |Y_P|, R \leq 10^9$.

It is guaranteed that there exists at least one solution satisfying all conditions. And if there are different solutions, print any one of them. The judge will regard two point's distance as $R$ if it is within an absolute error of $10^{-3}$ of $R$.

Sample Input

1 7 1 1 1 0 1 -1 0 1 -1 1 0 -1 -1 0

Sample Output

0 0 1

Hint

jiangzijing2015

Source

2017中国大学生程序设计竞赛-哈尔滨站-重现赛(感谢哈理工)

提交代码