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 (X_i, Y_i, Z_i), 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 X_i Y_i Z_i. (-1000 ≤ X_i, Y_i Z_i ≤ 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

0 -10 0
Output:
3 3 3
-5 -10 0
0 -10 0