C. Оптимальная точка
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Когда река принесла Герду к дому старой чародейки, та захотела сделать её своей приёмной дочерью. Чтобы Герда забыла про Кая, она волшебством убрала все розы из своего сада глубоко под землю.

Крот, живущий в саду, теперь может любоваться на розы, не вылезая на поверхность. Как известно, кроты слепы, но чародейка даровала этому кроту особое зрение. Он может видеть любые объекты под землёй, находящиеся на любом расстоянии от него и даже загороженные другими объектами. Но при этом то, насколько хорошо крот видит объект, зависит от манхэттенского расстояния до объекта.

Крот хочет найти оптимальную точку для наблюдения за розами, то есть такую точку, что её координаты являются целыми числами, а максимальное манхэттенское расстояние от неё до всех роз является минимально возможным.

Помогите ему найти оптимальную точку для наблюдения за розами.

Манхэттенским расстоянием между точками (x1,  y1,  z1) и (x2,  y2,  z2) называется величина |x1 - x2| + |y1 - y2| + |z1 - z2|.

Входные данные

В первой строке входных данных записано число t (1 ≤ t ≤ 100 000) — количество тестовых случаев. Затем следует ровно t блоков, каждый из которых описывает ровно один тест.

В первой строке каждого блока записано одно число ni (1 ≤ ni ≤ 100 000) — количество роз в тесте. Затем следует ровно ni строк, в каждой из которых задаётся три целых числа — координаты соответствующей розы. Обратите внимание, две и более роз могут быть расположены в одной точке.

Сумма всех ni не превосходит 100 000, все координаты по абсолютной величине не больше 1018.

Выходные данные

Для каждого из t тестовых случае выведите три целых числа — координаты оптимальной точки для наблюдения за розами в соответствующем тесте. Если оптимальных точек несколько, вы можете вывести любую из них.

Координаты оптимальной точки могут совпадать с координатами роз.

Примеры
Входные данные
1
5
0 0 4
0 0 -4
0 4 0
4 0 0
1 1 1
Выходные данные
0 0 0
Входные данные
2
1
3 5 9
2
3 5 9
3 5 9
Выходные данные
3 5 9
3 5 9
Примечание

В первом тесте максимальное манхэттенское расстояние равно 4.

Во втором тесте максимальное манхэттенское расстояние равно 0. Координаты роз могут совпадать как друг с другом, так и с оптимальной точкой.