#include <bits/stdc++.h>
using namespace std;
template <typename T>
T abs(T x) {
  return x > 0 ? x : -x;
}
template <typename T>
T sqr(T x) {
  return x * x;
}
template <typename T>
ostream &operator<<(ostream &s, const vector<T> &x) {
  s << "[";
  for (auto it : x) {
    s << it << ", ";
  }
  s << "]";
  return s;
}
template <typename T>
ostream &operator<<(ostream &s, const set<T> &x) {
  s << "{";
  for (auto it : x) {
    s << it << ", ";
  }
  s << "}";
  return s;
}
template <typename U, typename V>
ostream &operator<<(ostream &s, const pair<U, V> &x) {
  s << "(" << x.first << ", " << x.second << ")";
  return s;
}
template <typename T>
bool chmax(T &x, const T &y) {
  if (x < y) {
    x = y;
    return true;
  }
  return false;
}
template <typename T>
bool chmin(T &x, const T &y) {
  if (x > y) {
    x = y;
    return true;
  }
  return false;
}
struct point {
  long long x, y, z;
  point(long long x, long long y, long long z) : x(x), y(y), z(z) {}
  point() {}
};
bool maybe(long long c1, long long c2, long long c3, long long c4, long long &x,
           long long &y, long long &z) {
  if ((c2 & 1) != (c1 & 1) || (c3 & 1) != (c1 & 1) || (c4 & 1) != (c1 & 1))
    return false;
  long long c14 = c1 + c4, c23 = c2 + c3;
  if (c14 != c23) return false;
  x = c14 / 2;
  y = (c1 + c2 - 2 * x) / 2;
  z = c1 - x - y;
  return x + y - z == c2 && x - y + z == c3 && x - y - z == c4;
}
long long get_ans(long long x, long long y, long long z,
                  vector<point> &points) {
  long long ans = 0;
  for (auto p : points)
    ans = max(ans, abs(p.x - x) + abs(p.y - y) + abs(p.z - z));
  return ans;
}
const long long INF = 1e18;
long long norm(long long x) {
  if (x < -INF) return -INF;
  if (x > INF) return INF;
  return x;
}
bool check(long long c11, long long c12, long long c21, long long c22,
           long long c31, long long c32, long long c41, long long c42) {
  if (c11 > c22) return true;
  if (c31 > c42) return true;
  return false;
}
bool check(long long c11, long long c12, long long c21, long long c22,
           long long c31, long long c32, long long c41, long long c42,
           long long v, long long &x, long long &y, long long &z) {
  z = v;
  c11 -= z;
  c12 -= z;
  c21 += z;
  c22 += z;
  c31 -= z;
  c32 -= z;
  c41 += z;
  c42 += z;
  if (c11 > c22) return false;
  if (c31 > c42) return false;
  if (c21 > c12) return false;
  if (c41 > c32) return false;
  long long xpymini = max(c11, c21), xpymaxi = min(c12, c22);
  long long xmymini = max(c31, c41), xmymaxi = min(c32, c42);
  for (int i = 0; i < 2; i++)
    for (int j = 0; j < 2; j++)
      if (xpymini + i <= xpymaxi && xmymini + j <= xmymaxi &&
          (xpymini + i + xmymini + j) % 2 == 0) {
        x = (xpymini + i + xmymini + j) / 2;
        y = xpymini + i - x;
        return true;
      }
  return false;
}
point get_mans(long long c11, long long c12, long long c21, long long c22,
               long long c31, long long c32, long long c41, long long c42,
               vector<point> &points) {
  long long L = -INF;
  long long R = INF;
  while (R - L > 1) {
    long long c = (L + R) / 2;
    if (check(c11 - c, c12 - c, c21 + c, c22 + c, c31 - c, c32 - c, c41 + c,
              c42 + c))
      L = c;
    else
      R = c;
  }
  for (int delta = -2; delta <= 2; delta++) {
    long long v = L + delta;
    long long x = 0, y = 0, z = 0;
    if (check(c11, c12, c21, c22, c31, c32, c41, c42, v, x, y, z))
      return point(x, y, z);
  }
  return point(0, 0, 0);
}
bool intersect(long long x1, long long y1, long long x2, long long y2) {
  return max(x1, x2) <= min(y1, y2);
}
bool check2(long long c11, long long c12, long long c21, long long c22,
            long long c31, long long c32, long long c41, long long c42,
            long long dop, long long &x, long long &y, long long &z) {
  c11 -= dop, c12 += dop, c21 -= dop, c22 += dop, c31 -= dop, c32 += dop,
      c41 -= dop, c42 += dop;
  long long delta1 = c11 - c22;
  if (delta1 & 1) delta1++;
  long long delta2 = c12 - c21;
  if (delta2 & 1) delta2--;
  delta1 /= 2, delta2 /= 2;
  long long delta3 = c31 - c42;
  if (delta3 & 1) delta3++;
  long long delta4 = c32 - c41;
  if (delta4 & 1) delta4--;
  delta3 /= 2, delta4 /= 2;
  if (!intersect(delta1, delta2, delta3, delta4)) return false;
  long long mini = max(delta1, delta3), maxi = min(delta2, delta4);
  for (int i = 0; i < 2; i++) {
    if (mini + i > maxi) break;
    if (check(c11, c12, c21, c22, c31, c32, c41, c42, mini + i, x, y, z)) {
      return true;
    }
  }
  return false;
}
point get_cans(long long c11, long long c12, long long c21, long long c22,
               long long c31, long long c32, long long c41, long long c42,
               vector<point> &points) {
  long long delta1 = c11 - c22;
  if (delta1 & 1) delta1++;
  long long delta2 = c12 - c21;
  if (delta2 & 1) delta2--;
  delta1 /= 2, delta2 /= 2;
  long long delta3 = c31 - c42;
  if (delta3 & 1) delta3++;
  long long delta4 = c32 - c41;
  if (delta4 & 1) delta4--;
  delta3 /= 2, delta4 /= 2;
  long long dop = 0;
  if (delta1 > delta2 || delta3 > delta4)
    delta1--, delta2++, delta3--, delta4++, dop++;
  if (intersect(delta1, delta2, delta3, delta4)) {
    dop = dop;
  } else if (delta2 < delta3)
    dop += (delta3 - delta2 + 1) / 2;
  else if (delta4 < delta1)
    dop += (delta1 - delta4 + 1) / 2;
  for (int i = 0; i < 2; i++) {
    long long x, y, z;
    if (check2(c11, c12, c21, c22, c31, c32, c41, c42, dop + i, x, y, z)) {
      return point(x, y, z);
    }
  }
  assert(false);
  return point(0, 0, 0);
}
void solve() {
  int n;
  cin >> n;
  vector<point> points(n);
  for (int i = 0; i < n; i++) cin >> points[i].x >> points[i].y >> points[i].z;
  vector<vector<long long> > d(4);
  for (int msk = 0; msk < 4; msk++) {
    for (auto p : points) {
      long long sum = p.x + p.y + p.z;
      if (msk & 2) sum -= 2 * p.y;
      if (msk & 1) sum -= 2 * p.z;
      d[msk].push_back(sum);
    }
    sort(d[msk].begin(), d[msk].end());
  }
  vector<long long> c(4);
  long long maxi = 0;
  for (int i = 0; i < 4; i++) {
    c[i] = (d[i][0] + d[i][n - 1]) / 2;
    maxi = max(maxi, (d[i][n - 1] - d[i][0] + 1) / 2);
  }
  point ans = get_cans(d[0][n - 1] - maxi, d[0][0] + maxi, d[1][n - 1] - maxi,
                       d[1][0] + maxi, d[2][n - 1] - maxi, d[2][0] + maxi,
                       d[3][n - 1] - maxi, d[3][0] + maxi, points);
  cout << norm(ans.x) << " " << norm(ans.y) << " " << norm(ans.z) << "\n";
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int T;
  cin >> T;
  while (T--) {
    solve();
  }
  return 0;
}

### Prompt

Create a solution in Cpp for the following problem:

When the river brought Gerda to the house of the Old Lady who Knew Magic, this lady decided to make Gerda her daughter. She wants Gerda to forget about Kay, so she puts all the roses from the garden underground.

Mole, who lives in this garden, now can watch the roses without going up to the surface. Typical mole is blind, but this mole was granted as special vision by the Old Lady. He can watch any underground objects on any distance, even through the obstacles and other objects. However, the quality of the picture depends on the Manhattan distance to object being observed.

Mole wants to find an optimal point to watch roses, that is such point with integer coordinates that the maximum Manhattan distance to the rose is minimum possible.

As usual, he asks you to help.

Manhattan distance between points (x1, y1, z1) and (x2, y2, z2) is defined as |x1 - x2| + |y1 - y2| + |z1 - z2|.

Input

The first line of the input contains an integer t t (1 ≤ t ≤ 100 000) — the number of test cases. Then follow exactly t blocks, each containing the description of exactly one test.

The first line of each block contains an integer ni (1 ≤ ni ≤ 100 000) — the number of roses in the test. Then follow ni lines, containing three integers each — the coordinates of the corresponding rose. Note that two or more roses may share the same position.

It's guaranteed that the sum of all ni doesn't exceed 100 000 and all coordinates are not greater than 1018 by their absolute value.

Output

For each of t test cases print three integers — the coordinates of the optimal point to watch roses. If there are many optimal answers, print any of them.

The coordinates of the optimal point may coincide with the coordinates of any rose.

Examples

Input

1
5
0 0 4
0 0 -4
0 4 0
4 0 0
1 1 1


Output

0 0 0


Input

2
1
3 5 9
2
3 5 9
3 5 9


Output

3 5 9
3 5 9

Note

In the first sample, the maximum Manhattan distance from the point to the rose is equal to 4.

In the second sample, the maximum possible distance is 0. Note that the positions of the roses may coincide with each other and with the position of the optimal point.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
template <typename T>
T abs(T x) {
  return x > 0 ? x : -x;
}
template <typename T>
T sqr(T x) {
  return x * x;
}
template <typename T>
ostream &operator<<(ostream &s, const vector<T> &x) {
  s << "[";
  for (auto it : x) {
    s << it << ", ";
  }
  s << "]";
  return s;
}
template <typename T>
ostream &operator<<(ostream &s, const set<T> &x) {
  s << "{";
  for (auto it : x) {
    s << it << ", ";
  }
  s << "}";
  return s;
}
template <typename U, typename V>
ostream &operator<<(ostream &s, const pair<U, V> &x) {
  s << "(" << x.first << ", " << x.second << ")";
  return s;
}
template <typename T>
bool chmax(T &x, const T &y) {
  if (x < y) {
    x = y;
    return true;
  }
  return false;
}
template <typename T>
bool chmin(T &x, const T &y) {
  if (x > y) {
    x = y;
    return true;
  }
  return false;
}
struct point {
  long long x, y, z;
  point(long long x, long long y, long long z) : x(x), y(y), z(z) {}
  point() {}
};
bool maybe(long long c1, long long c2, long long c3, long long c4, long long &x,
           long long &y, long long &z) {
  if ((c2 & 1) != (c1 & 1) || (c3 & 1) != (c1 & 1) || (c4 & 1) != (c1 & 1))
    return false;
  long long c14 = c1 + c4, c23 = c2 + c3;
  if (c14 != c23) return false;
  x = c14 / 2;
  y = (c1 + c2 - 2 * x) / 2;
  z = c1 - x - y;
  return x + y - z == c2 && x - y + z == c3 && x - y - z == c4;
}
long long get_ans(long long x, long long y, long long z,
                  vector<point> &points) {
  long long ans = 0;
  for (auto p : points)
    ans = max(ans, abs(p.x - x) + abs(p.y - y) + abs(p.z - z));
  return ans;
}
const long long INF = 1e18;
long long norm(long long x) {
  if (x < -INF) return -INF;
  if (x > INF) return INF;
  return x;
}
bool check(long long c11, long long c12, long long c21, long long c22,
           long long c31, long long c32, long long c41, long long c42) {
  if (c11 > c22) return true;
  if (c31 > c42) return true;
  return false;
}
bool check(long long c11, long long c12, long long c21, long long c22,
           long long c31, long long c32, long long c41, long long c42,
           long long v, long long &x, long long &y, long long &z) {
  z = v;
  c11 -= z;
  c12 -= z;
  c21 += z;
  c22 += z;
  c31 -= z;
  c32 -= z;
  c41 += z;
  c42 += z;
  if (c11 > c22) return false;
  if (c31 > c42) return false;
  if (c21 > c12) return false;
  if (c41 > c32) return false;
  long long xpymini = max(c11, c21), xpymaxi = min(c12, c22);
  long long xmymini = max(c31, c41), xmymaxi = min(c32, c42);
  for (int i = 0; i < 2; i++)
    for (int j = 0; j < 2; j++)
      if (xpymini + i <= xpymaxi && xmymini + j <= xmymaxi &&
          (xpymini + i + xmymini + j) % 2 == 0) {
        x = (xpymini + i + xmymini + j) / 2;
        y = xpymini + i - x;
        return true;
      }
  return false;
}
point get_mans(long long c11, long long c12, long long c21, long long c22,
               long long c31, long long c32, long long c41, long long c42,
               vector<point> &points) {
  long long L = -INF;
  long long R = INF;
  while (R - L > 1) {
    long long c = (L + R) / 2;
    if (check(c11 - c, c12 - c, c21 + c, c22 + c, c31 - c, c32 - c, c41 + c,
              c42 + c))
      L = c;
    else
      R = c;
  }
  for (int delta = -2; delta <= 2; delta++) {
    long long v = L + delta;
    long long x = 0, y = 0, z = 0;
    if (check(c11, c12, c21, c22, c31, c32, c41, c42, v, x, y, z))
      return point(x, y, z);
  }
  return point(0, 0, 0);
}
bool intersect(long long x1, long long y1, long long x2, long long y2) {
  return max(x1, x2) <= min(y1, y2);
}
bool check2(long long c11, long long c12, long long c21, long long c22,
            long long c31, long long c32, long long c41, long long c42,
            long long dop, long long &x, long long &y, long long &z) {
  c11 -= dop, c12 += dop, c21 -= dop, c22 += dop, c31 -= dop, c32 += dop,
      c41 -= dop, c42 += dop;
  long long delta1 = c11 - c22;
  if (delta1 & 1) delta1++;
  long long delta2 = c12 - c21;
  if (delta2 & 1) delta2--;
  delta1 /= 2, delta2 /= 2;
  long long delta3 = c31 - c42;
  if (delta3 & 1) delta3++;
  long long delta4 = c32 - c41;
  if (delta4 & 1) delta4--;
  delta3 /= 2, delta4 /= 2;
  if (!intersect(delta1, delta2, delta3, delta4)) return false;
  long long mini = max(delta1, delta3), maxi = min(delta2, delta4);
  for (int i = 0; i < 2; i++) {
    if (mini + i > maxi) break;
    if (check(c11, c12, c21, c22, c31, c32, c41, c42, mini + i, x, y, z)) {
      return true;
    }
  }
  return false;
}
point get_cans(long long c11, long long c12, long long c21, long long c22,
               long long c31, long long c32, long long c41, long long c42,
               vector<point> &points) {
  long long delta1 = c11 - c22;
  if (delta1 & 1) delta1++;
  long long delta2 = c12 - c21;
  if (delta2 & 1) delta2--;
  delta1 /= 2, delta2 /= 2;
  long long delta3 = c31 - c42;
  if (delta3 & 1) delta3++;
  long long delta4 = c32 - c41;
  if (delta4 & 1) delta4--;
  delta3 /= 2, delta4 /= 2;
  long long dop = 0;
  if (delta1 > delta2 || delta3 > delta4)
    delta1--, delta2++, delta3--, delta4++, dop++;
  if (intersect(delta1, delta2, delta3, delta4)) {
    dop = dop;
  } else if (delta2 < delta3)
    dop += (delta3 - delta2 + 1) / 2;
  else if (delta4 < delta1)
    dop += (delta1 - delta4 + 1) / 2;
  for (int i = 0; i < 2; i++) {
    long long x, y, z;
    if (check2(c11, c12, c21, c22, c31, c32, c41, c42, dop + i, x, y, z)) {
      return point(x, y, z);
    }
  }
  assert(false);
  return point(0, 0, 0);
}
void solve() {
  int n;
  cin >> n;
  vector<point> points(n);
  for (int i = 0; i < n; i++) cin >> points[i].x >> points[i].y >> points[i].z;
  vector<vector<long long> > d(4);
  for (int msk = 0; msk < 4; msk++) {
    for (auto p : points) {
      long long sum = p.x + p.y + p.z;
      if (msk & 2) sum -= 2 * p.y;
      if (msk & 1) sum -= 2 * p.z;
      d[msk].push_back(sum);
    }
    sort(d[msk].begin(), d[msk].end());
  }
  vector<long long> c(4);
  long long maxi = 0;
  for (int i = 0; i < 4; i++) {
    c[i] = (d[i][0] + d[i][n - 1]) / 2;
    maxi = max(maxi, (d[i][n - 1] - d[i][0] + 1) / 2);
  }
  point ans = get_cans(d[0][n - 1] - maxi, d[0][0] + maxi, d[1][n - 1] - maxi,
                       d[1][0] + maxi, d[2][n - 1] - maxi, d[2][0] + maxi,
                       d[3][n - 1] - maxi, d[3][0] + maxi, points);
  cout << norm(ans.x) << " " << norm(ans.y) << " " << norm(ans.z) << "\n";
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int T;
  cin >> T;
  while (T--) {
    solve();
  }
  return 0;
}

```