TRFPLN - Traffic Planning

Most of the traffic accidents occur at road intersections. In order to deal with the traffic accidents efficiently, the traffic police should arrive at the accidental scene quickly. You, as an urban planner, are entrusted to select the best location in the urban area to build the traffic police station.

You are given N coordinates (Xi, Yi, Zi), where X, Y describe the 2D position and Z is  the height of terrain, representing those road intersections that always have traffic accidents. To simplify the problem, best location means a given road intersection(s) that minimizes the sum of distances to all other given intersections. That is, you will choose a given road intersection(s) as potential location to build the station. Please note that the traffic police can only move along the road horizontally and vertically, but not diagonally which will be blocked by buildings. The length of each street block is 1, and all roads are connected in grid pattern.

Input

The first line of input is the number of test cases T. (1 ≤ T ≤ 50)

For each test case, the first line is the numbers of road intersections that always have traffic accidents N. (1 ≤ N ≤ 1000)

The following N lines are the coordinates of each road intersection Xi Yi Zi. (-1000 ≤ Xi, Yi Zi ≤ 1000)

It is guaranteed that no coordinates are duplicate.

Output

For each test case, output the coordinates X Y Z of selected road intersection(s) to build the traffic police station. If there is more than one best location, output all of them according to the input order line by line.

After each test case, print a blank line.

Example

Input: 
2

7
2 6 3
1 -5 0
-100 -10 3
3 3 3
0 150 9
999 -3 0
878 123 4

2
-5 -10 0
0 -10 0

Output:
3 3 3

-5 -10 0
0 -10 0


Added by:him0727
Date:2018-03-27
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:Own problem

hide comments
2019-12-19 17:04:08 :D
How should we count the distance here? Should differences between heights be taken into account? Also, can there be two intersections with the same xi and yi but different zi?

RE:
1. It is the sum of the absolute differences of x, y, z
2. Yes
3. It is possible

RE: RE:
Thanks. Aside for a little cryptic description, a very nice problem. Thanks for setting it up.

Last edit: 2019-12-21 16:07:00
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.