Problem J
Traveling in
another dimension
Input: standard input
Output: standard output
Many of us would like to break the barrier of dimensions but the fact is that this is not that easy. Some consider Time as the fourth dimension and many others have other ideas. Some just ignore the concept of time. Our scientist friend Arnold has discovered some ways to travel in four dimensions. But the problem is that he being a three-dimensional animal has to spent more energy to go from one point to another in four-dimensional space and this energy is proportional to the square of the distance between the two points. Arnold has taken many of his friends to the four-dimensional world. The problems they face are:
a) Safety problem: The four-dimensional creatures come from nowhere and hit them. It is very difficult for them to track the four-dimensional creatures.
b) Losing way: They always lose their way in the four dimensions.
To avoid this problems they have made a tracking device and has discovered the moving paths of the four dimensional creatures and also has discovered a straight line (a four dimensional straight line is of the form Aw + Bx+ Cy+ Dz+ E=0) which is very safe. They started building house on or beside the line. They transformed the coordinate system along the safe line and used a single dimensional coordinate system on the line. So if two points has coordinates d1 and d2 the distance between them is |d1-d2| and the cost to go from one point to another is proportional to the square of the distance between them. Now given the coordinates of Arnold's friends' houses you have to find out the coordinate of Arnold's house. Arnold builds his house in such a place from where his effort of visiting his friends' house will be minimum. Initially Arnold is in his home. Arnold visits a friend's house then returns home then go to another friend's house and so on. His final position is also in his home. Note that as they are all three-dimensional creatures so their houses are also three-dimensional. So in the same place in four dimension there can be more than one house.
Input
The input contains several blocks. Each block contains an integer N (N>=0 && N<=10000) indicating the number of Arnold's friends in the four dimension and then contains the N coordinates of their houses. The input is terminated by the end of file.
Output
The output contains Arnold's coordinate. If Arnold's coordinate cannot be determined print a –1 (minus one). The outputs for each block will be in separate lines. The output format is shown in the sample output.
Sample Input:
Sample Output: