Когда река принесла Герду к дому старой чародейки, та захотела сделать её своей приёмной дочерью. Чтобы Герда забыла про Кая, она волшебством убрала все розы из своего сада глубоко под землю.
Крот, живущий в саду, теперь может любоваться на розы, не вылезая на поверхность. Как известно, кроты слепы, но чародейка даровала этому кроту особое зрение. Он может видеть любые объекты под землёй, находящиеся на любом расстоянии от него и даже загороженные другими объектами. Но при этом то, насколько хорошо крот видит объект, зависит от манхэттенского расстояния до объекта.
Крот хочет найти оптимальную точку для наблюдения за розами, то есть такую точку, что её координаты являются целыми числами, а максимальное манхэттенское расстояние от неё до всех роз является минимально возможным.
Помогите ему найти оптимальную точку для наблюдения за розами.
Манхэттенским расстоянием между точками (x1, y1, z1) и (x2, y2, z2) называется величина |x1 - x2| + |y1 - y2| + |z1 - z2|.
Выходные данные
Для каждого из t тестовых случае выведите три целых числа — координаты оптимальной точки для наблюдения за розами в соответствующем тесте. Если оптимальных точек несколько, вы можете вывести любую из них.
Координаты оптимальной точки могут совпадать с координатами роз.
Примечание
В первом тесте максимальное манхэттенское расстояние равно 4.
Во втором тесте максимальное манхэттенское расстояние равно 0. Координаты роз могут совпадать как друг с другом, так и с оптимальной точкой.