#include <bits/stdc++.h>
using namespace std;
template <typename T>
bool chkmax(T &x, T y) {
  return x < y ? x = y, true : false;
}
template <typename T>
bool chkmin(T &x, T y) {
  return x > y ? x = y, true : false;
}
int readint() {
  int x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
int n, cnta, cntb;
int a[5], b[5], x[5], y[5], now[5], cnt[5], t[5];
pair<int, int> t1[5], t2[5], ans[5];
int getdiv(long long d, bool kp) {
  if (a[1] > a[2]) swap(a[1], a[2]);
  if (b[1] > b[2]) swap(b[1], b[2]);
  int l = 0, r = 1e9, ret = -1, st = 0;
  while (l <= r) {
    int mid = (l + r) / 2;
    int l1 = a[1] - mid, r1 = a[1] + mid;
    int l2 = b[1] - mid, r2 = b[1] + mid;
    int l3 = a[2] - d - mid, r3 = a[2] - d + mid;
    int l4 = b[2] - d - mid, r4 = b[2] - d + mid;
    if (max(max(l1, l2), max(l3, l4)) <= min(min(r1, r2), min(r3, r4))) {
      ret = mid, r = mid - 1;
      if (kp) st = max(max(l1, l2), max(l3, l4));
    } else
      l = mid + 1;
  }
  if (kp) {
    for (int i = 0; i < 4; i++)
      if (x[i] == t[0] && y[i] == a[1]) ans[i] = make_pair(x[i], st);
    for (int i = 0; i < 4; i++)
      if (x[i] == t[0] && y[i] == a[2]) ans[i] = make_pair(x[i], st + d);
    for (int i = 0; i < 4; i++)
      if (x[i] == t[2] && y[i] == b[1]) ans[i] = make_pair(x[i], st);
    for (int i = 0; i < 4; i++)
      if (x[i] == t[2] && y[i] == b[2]) ans[i] = make_pair(x[i], st + d);
  }
  return ret;
}
int solve(int tx, bool kp) {
  for (int i = 0; i < 4; i++) now[i] = (tx >> i) & 1;
  cnt[0] = cnt[1] = 0;
  for (int i = 0; i < 4; i++) cnt[now[i]]++;
  if (cnt[0] == 2 && cnt[1] == 2) {
    int cnt1 = 0, cnt2 = 0;
    for (int i = 0; i < 4; i++) {
      if (!now[i])
        t1[++cnt1] = make_pair(x[i], y[i]);
      else
        t2[++cnt2] = make_pair(x[i], y[i]);
    }
    if (t1[1].first == t1[2].first) {
      for (int i = 0; i < 4; i++) swap(x[i], y[i]);
      for (int i = 1; i <= cnt1; i++) swap(t1[i].first, t1[i].second);
      for (int i = 1; i <= cnt2; i++) swap(t2[i].first, t2[i].second);
      swap(t1, t2);
      for (int i = 0; i < 4; i++) now[i] ^= 1;
      int res = max(
          abs(min(t2[1].first, t2[2].first) - min(t1[1].first, t1[2].first)),
          abs(max(t2[1].first, t2[2].first) - max(t1[1].first, t1[2].first)));
      int tres = 1 << 30, opt = 0,
          ty = t2[1].second + fabs(t1[1].first - t1[2].first);
      if (chkmin(tres, max(abs(t1[1].second - ty), abs(t1[2].second - ty))))
        opt = 1;
      ty = t2[1].second - fabs(t1[1].first - t1[2].first);
      if (chkmin(tres, max(abs(t1[1].second - ty), abs(t1[2].second - ty))))
        opt = 2;
      if (kp) {
        if (opt == 1) {
          ty = t2[1].second + fabs(t1[1].first - t1[2].first);
          for (int i = 0; i < 4; i++)
            if (now[i] && x[i] == min(t2[1].first, t2[2].first))
              ans[i] = make_pair(min(t1[1].first, t1[2].first), y[i]);
          for (int i = 0; i < 4; i++)
            if (now[i] && x[i] == max(t2[1].first, t2[2].first))
              ans[i] = make_pair(max(t1[1].first, t1[2].first), y[i]);
          for (int i = 0; i < 4; i++)
            if (!now[i]) ans[i] = make_pair(x[i], ty);
          for (int i = 0; i < 4; i++)
            if (!now[i]) ans[i] = make_pair(x[i], ty);
        } else {
          ty = t2[1].second - fabs(t1[1].first - t1[2].first);
          for (int i = 0; i < 4; i++)
            if (now[i] && x[i] == min(t2[1].first, t2[2].first))
              ans[i] = make_pair(min(t1[1].first, t1[2].first), y[i]);
          for (int i = 0; i < 4; i++)
            if (now[i] && x[i] == max(t2[1].first, t2[2].first))
              ans[i] = make_pair(max(t1[1].first, t1[2].first), y[i]);
          for (int i = 0; i < 4; i++)
            if (!now[i]) ans[i] = make_pair(x[i], ty);
          for (int i = 0; i < 4; i++)
            if (!now[i]) ans[i] = make_pair(x[i], ty);
        }
        for (int i = 0; i < 4; i++)
          printf("%d %d\n", ans[i].second, ans[i].first);
      }
      for (int i = 0; i < 4; i++) swap(x[i], y[i]);
      return max(tres, res);
    } else if (t2[1].second == t2[2].second) {
      int res = max(
          fabs(min(t2[1].first, t2[2].first) - min(t1[1].first, t1[2].first)),
          fabs(max(t2[1].first, t2[2].first) - max(t1[1].first, t1[2].first)));
      int tres = 1 << 30, opt = 0,
          ty = t2[1].second + fabs(t1[1].first - t1[2].first);
      if (chkmin(tres, max(abs(t1[1].second - ty), abs(t1[2].second - ty))))
        opt = 1;
      ty = t2[1].second - fabs(t1[1].first - t1[2].first);
      if (chkmin(tres, max(abs(t1[1].second - ty), abs(t1[2].second - ty))))
        opt = 2;
      if (kp) {
        if (opt == 1) {
          ty = t2[1].second + fabs(t1[1].first - t1[2].first);
          for (int i = 0; i < 4; i++)
            if (now[i] && x[i] == min(t2[1].first, t2[2].first))
              ans[i] = make_pair(min(t1[1].first, t1[2].first), y[i]);
          for (int i = 0; i < 4; i++)
            if (now[i] && x[i] == max(t2[1].first, t2[2].first))
              ans[i] = make_pair(max(t1[1].first, t1[2].first), y[i]);
          for (int i = 0; i < 4; i++)
            if (!now[i]) ans[i] = make_pair(x[i], ty);
          for (int i = 0; i < 4; i++)
            if (!now[i]) ans[i] = make_pair(x[i], ty);
        } else {
          ty = t2[1].second - fabs(t1[1].first - t1[2].first);
          for (int i = 0; i < 4; i++)
            if (now[i] && x[i] == min(t2[1].first, t2[2].first))
              ans[i] = make_pair(min(t1[1].first, t1[2].first), y[i]);
          for (int i = 0; i < 4; i++)
            if (now[i] && x[i] == max(t2[1].first, t2[2].first))
              ans[i] = make_pair(max(t1[1].first, t1[2].first), y[i]);
          for (int i = 0; i < 4; i++)
            if (!now[i]) ans[i] = make_pair(x[i], ty);
          for (int i = 0; i < 4; i++)
            if (!now[i]) ans[i] = make_pair(x[i], ty);
        }
        for (int i = 0; i < 4; i++)
          printf("%d %d\n", ans[i].first, ans[i].second);
      }
      return max(tres, res);
    }
    if (fabs(t1[2].first - t1[1].first) != fabs(t2[2].second - t2[1].second))
      return 1 << 30;
    int res = 1 << 30, opt = 0;
    if (chkmin(res, max(max(abs(t1[1].second - t2[1].second),
                            abs(t1[2].second - t2[2].second)),
                        max(abs(t2[1].first - t1[2].first),
                            abs(t2[2].first - t1[1].first)))))
      opt = 1;
    if (chkmin(res, max(max(abs(t1[1].second - t2[2].second),
                            abs(t1[2].second - t2[1].second)),
                        max(abs(t2[1].first - t1[1].first),
                            abs(t2[2].first - t1[2].first)))))
      opt = 2;
    if (kp) {
      if (opt == 1) {
        for (int i = 0; i < 4; i++)
          if (make_pair(x[i], y[i]) == t1[1])
            ans[i] = make_pair(t1[1].first, t2[1].second);
        for (int i = 0; i < 4; i++)
          if (make_pair(x[i], y[i]) == t1[2])
            ans[i] = make_pair(t1[2].first, t2[2].second);
        for (int i = 0; i < 4; i++)
          if (make_pair(x[i], y[i]) == t2[1])
            ans[i] = make_pair(t1[2].first, t2[1].second);
        for (int i = 0; i < 4; i++)
          if (make_pair(x[i], y[i]) == t2[2])
            ans[i] = make_pair(t1[1].first, t2[2].second);
      } else {
        for (int i = 0; i < 4; i++)
          if (make_pair(x[i], y[i]) == t1[1])
            ans[i] = make_pair(t1[1].first, t2[2].second);
        for (int i = 0; i < 4; i++)
          if (make_pair(x[i], y[i]) == t1[2])
            ans[i] = make_pair(t1[2].first, t2[1].second);
        for (int i = 0; i < 4; i++)
          if (make_pair(x[i], y[i]) == t2[1])
            ans[i] = make_pair(t1[1].first, t2[1].second);
        for (int i = 0; i < 4; i++)
          if (make_pair(x[i], y[i]) == t2[2])
            ans[i] = make_pair(t1[2].first, t2[2].second);
      }
      for (int i = 0; i < 4; i++)
        printf("%d %d\n", ans[i].first, ans[i].second);
    }
    return res;
  } else if (cnt[0] > cnt[1]) {
    if (cnt[0] == 4) {
      for (int i = 0; i < 4; i++) t[i] = x[i];
      sort(t, t + 4);
      if (t[0] != t[1] || t[2] != t[3] || t[1] == t[2]) return 1 << 30;
      cnta = cntb = 0;
      for (int i = 0; i < 4; i++) {
        if (x[i] == t[1])
          a[++cnta] = y[i];
        else
          b[++cntb] = y[i];
      }
      int ret = getdiv(fabs(t[2] - t[0]), kp);
      if (kp) {
        for (int i = 0; i < 4; i++)
          printf("%d %d\n", ans[i].first, ans[i].second);
      }
      return ret;
    } else {
      int tcnt = 0, pl = 0, ply = 0;
      for (int i = 0; i < 4; i++) {
        if (!now[i])
          t[tcnt++] = x[i];
        else
          pl = x[i], ply = y[i];
      }
      sort(t, t + 3);
      if (t[0] != t[1] && t[1] != t[2]) return 1 << 30;
      if (t[0] != t[1]) swap(t[0], t[2]);
      cnta = cntb = 0;
      for (int i = 0; i < 4; i++) {
        if (now[i]) continue;
        if (x[i] == t[0])
          a[++cnta] = y[i];
        else
          b[++cntb] = y[i];
      }
      int res = fabs(pl - t[2]), tres = 1 << 30;
      int ty = ply - fabs(t[0] - t[2]), opt = 0;
      if (chkmin(tres, max(abs(b[1] - ty),
                           min(max(abs(a[1] - ply), abs(a[2] - ty)),
                               max(abs(a[2] - ply), abs(a[1] - ty))))))
        opt = 1;
      ty = ply + fabs(t[0] - t[2]);
      if (chkmin(tres, max(abs(b[1] - ty),
                           min(max(abs(a[1] - ply), abs(a[2] - ty)),
                               max(abs(a[2] - ply), abs(a[1] - ty))))))
        opt = 2;
      if (kp) {
        if (opt == 1) {
          ty = ply - fabs(t[0] - t[2]);
          if (max(abs(a[1] - ply), abs(a[2] - ty)) <
              max(abs(a[2] - ply), abs(a[1] - ty))) {
            for (int i = 0; i < 4; i++)
              if (now[i]) ans[i] = make_pair(t[2], y[i]);
            for (int i = 0; i < 4; i++) {
              if (now[i]) continue;
              if (x[i] == t[2])
                ans[i] = make_pair(x[i], ty);
              else if (x[i] == t[0] && y[i] == a[1])
                ans[i] = make_pair(x[i], ply);
              else if (x[i] == t[0] && y[i] == a[2])
                ans[i] = make_pair(x[i], ty);
            }
          } else {
            for (int i = 0; i < 4; i++)
              if (now[i]) ans[i] = make_pair(t[2], y[i]);
            for (int i = 0; i < 4; i++) {
              if (now[i]) continue;
              if (x[i] == t[2])
                ans[i] = make_pair(x[i], ty);
              else if (x[i] == t[0] && y[i] == a[1])
                ans[i] = make_pair(x[i], ty);
              else if (x[i] == t[0] && y[i] == a[2])
                ans[i] = make_pair(x[i], ply);
            }
          }
        } else {
          ty = ply + fabs(t[0] - t[2]);
          if (max(abs(a[1] - ply), abs(a[2] - ty)) <
              max(abs(a[2] - ply), abs(a[1] - ty))) {
            for (int i = 0; i < 4; i++)
              if (now[i]) ans[i] = make_pair(t[2], y[i]);
            for (int i = 0; i < 4; i++) {
              if (now[i]) continue;
              if (x[i] == t[2])
                ans[i] = make_pair(x[i], ty);
              else if (x[i] == t[0] && y[i] == a[1])
                ans[i] = make_pair(x[i], ply);
              else if (x[i] == t[0] && y[i] == a[2])
                ans[i] = make_pair(x[i], ty);
            }
          } else {
            for (int i = 0; i < 4; i++)
              if (now[i]) ans[i] = make_pair(t[2], y[i]);
            for (int i = 0; i < 4; i++) {
              if (now[i]) continue;
              if (x[i] == t[2])
                ans[i] = make_pair(x[i], ty);
              else if (x[i] == t[0] && y[i] == a[1])
                ans[i] = make_pair(x[i], ty);
              else if (x[i] == t[0] && y[i] == a[2])
                ans[i] = make_pair(x[i], ply);
            }
          }
        }
        for (int i = 0; i < 4; i++)
          printf("%d %d\n", ans[i].first, ans[i].second);
      }
      return max(tres, res);
    }
  } else {
    for (int i = 0; i < 4; i++) now[i] ^= 1;
    swap(cnt[0], cnt[1]);
    for (int i = 0; i < 4; i++) swap(x[i], y[i]);
    if (cnt[0] == 4) {
      for (int i = 0; i < 4; i++) t[i] = x[i];
      sort(t, t + 4);
      if (t[0] != t[1] || t[2] != t[3] || t[1] == t[2]) {
        for (int i = 0; i < 4; i++) swap(x[i], y[i]);
        return 1 << 30;
      }
      cnta = cntb = 0;
      for (int i = 0; i < 4; i++) {
        if (x[i] == t[1])
          a[++cnta] = y[i];
        else
          b[++cntb] = y[i];
      }
      int ret = getdiv(fabs(t[2] - t[0]), kp);
      for (int i = 0; i < 4; i++) swap(x[i], y[i]);
      if (kp) {
        for (int i = 0; i < 4; i++)
          printf("%d %d\n", ans[i].second, ans[i].first);
      }
      return ret;
    } else {
      int tcnt = 0, pl = 0, ply = 0;
      for (int i = 0; i < 4; i++) {
        if (!now[i])
          t[tcnt++] = x[i];
        else
          pl = x[i], ply = y[i];
      }
      sort(t, t + 3);
      if (t[0] != t[1] && t[1] != t[2]) {
        for (int i = 0; i < 4; i++) swap(x[i], y[i]);
        return 1 << 30;
      }
      if (t[0] != t[1]) swap(t[0], t[2]);
      cnta = cntb = 0;
      for (int i = 0; i < 4; i++) {
        if (now[i]) continue;
        if (x[i] == t[0])
          a[++cnta] = y[i];
        else
          b[++cntb] = y[i];
      }
      int res = fabs(pl - t[2]), tres = 1 << 30;
      int ty = ply - fabs(t[0] - t[2]), opt = 0;
      if (chkmin(tres, max(abs(b[1] - ty),
                           min(max(abs(a[1] - ply), abs(a[2] - ty)),
                               max(abs(a[2] - ply), abs(a[1] - ty))))))
        opt = 1;
      ty = ply + fabs(t[0] - t[2]);
      if (chkmin(tres, max(abs(b[1] - ty),
                           min(max(abs(a[1] - ply), abs(a[2] - ty)),
                               max(abs(a[2] - ply), abs(a[1] - ty))))))
        opt = 2;
      if (kp) {
        if (opt == 1) {
          ty = ply - fabs(t[0] - t[2]);
          if (max(abs(a[1] - ply), abs(a[2] - ty)) <
              max(abs(a[2] - ply), abs(a[1] - ty))) {
            for (int i = 0; i < 4; i++)
              if (now[i]) ans[i] = make_pair(t[2], y[i]);
            for (int i = 0; i < 4; i++) {
              if (now[i]) continue;
              if (x[i] == t[2])
                ans[i] = make_pair(x[i], ty);
              else if (x[i] == t[0] && y[i] == a[1])
                ans[i] = make_pair(x[i], ply);
              else if (x[i] == t[0] && y[i] == a[2])
                ans[i] = make_pair(x[i], ty);
            }
          } else {
            for (int i = 0; i < 4; i++)
              if (now[i]) ans[i] = make_pair(t[2], y[i]);
            for (int i = 0; i < 4; i++) {
              if (now[i]) continue;
              if (x[i] == t[2])
                ans[i] = make_pair(x[i], ty);
              else if (x[i] == t[0] && y[i] == a[1])
                ans[i] = make_pair(x[i], ty);
              else if (x[i] == t[0] && y[i] == a[2])
                ans[i] = make_pair(x[i], ply);
            }
          }
        } else {
          ty = ply + fabs(t[0] - t[2]);
          if (max(abs(a[1] - ply), abs(a[2] - ty)) <
              max(abs(a[2] - ply), abs(a[1] - ty))) {
            for (int i = 0; i < 4; i++)
              if (now[i]) ans[i] = make_pair(t[2], y[i]);
            for (int i = 0; i < 4; i++) {
              if (now[i]) continue;
              if (x[i] == t[2])
                ans[i] = make_pair(x[i], ty);
              else if (x[i] == t[0] && y[i] == a[1])
                ans[i] = make_pair(x[i], ply);
              else if (x[i] == t[0] && y[i] == a[2])
                ans[i] = make_pair(x[i], ty);
            }
          } else {
            for (int i = 0; i < 4; i++)
              if (now[i]) ans[i] = make_pair(t[2], y[i]);
            for (int i = 0; i < 4; i++) {
              if (now[i]) continue;
              if (x[i] == t[2])
                ans[i] = make_pair(x[i], ty);
              else if (x[i] == t[0] && y[i] == a[1])
                ans[i] = make_pair(x[i], ty);
              else if (x[i] == t[0] && y[i] == a[2])
                ans[i] = make_pair(x[i], ply);
            }
          }
        }
        for (int i = 0; i < 4; i++)
          printf("%d %d\n", ans[i].second, ans[i].first);
      }
      for (int i = 0; i < 4; i++) swap(x[i], y[i]);
      return max(tres, res);
    }
  }
}
int main() {
  int T = readint();
  while (T--) {
    for (int i = 0; i < 4; i++) x[i] = readint(), y[i] = readint();
    int cho = 0, res = 1 << 30;
    for (int i = 0; i < (1 << 4); i++)
      if (chkmin(res, solve(i, 0))) cho = i;
    if (res == (1 << 30))
      printf("-1\n");
    else {
      printf("%d\n", res);
      solve(cho, 1);
    }
  }
  return 0;
}

### Prompt

Your challenge is to write a Cpp solution to the following problem:

Group of Berland scientists, with whom you have a close business relationship, makes a research in the area of peaceful nuclear energy. In particular, they found that a group of four nanobots, placed on a surface of a plate, can run a powerful chain reaction under certain conditions. 

To be precise, researchers introduced a rectangular Cartesian coordinate system on a flat plate and selected four distinct points with integer coordinates where bots will be placed initially. Next each bot will be assigned with one of the four directions (up, down, left or right) parallel to the coordinate axes. After that, each bot is shifted by an integer distance (which may be different for different bots) along its direction. The chain reaction starts, if the bots are in the corners of a square with positive area with sides parallel to the coordinate axes. Each corner of the square must contain one nanobot. This reaction will be stronger, if bots spend less time to move. We can assume that bots move with unit speed. In other words, the lesser is the maximum length traveled by bot, the stronger is reaction.

Scientists have prepared a set of plates and selected starting position for the bots for each plate. Now they ask you to assign the direction for each bot to move after landing such that the maximum length traveled by bot is as small as possible.

Input

The first line contains an integer number t (1 ≤ t ≤ 50) — the number of plates.

t descriptions of plates follow. A description of each plate consists of four lines. Each line consists of a pair of integers numbers xi, yi ( - 108 ≤ xi, yi ≤ 108) — coordinates of the next bot. All bots are in different locations.

Note, though, the problem can include several records in one test, you can hack other people's submissions only with the test of one plate, i.e. parameter t in a hack test should be equal to 1.

Output

Print answers for all plates separately. First goes a single integer number in a separate line. If scientists have made an unfortunate mistake and nanobots are not able to form the desired square, print -1. Otherwise, print the minimum possible length of the longest bot's path.

If a solution exists, in the next four lines print two integer numbers — positions of each bot after moving. Print bots' positions in the order they are specified in the input data.

If there are multiple solution, you can print any of them.

Examples

Input

2
1 1
1 -1
-1 1
-1 -1
1 1
2 2
4 4
6 6


Output

0
1 1
1 -1
-1 1
-1 -1
-1

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
template <typename T>
bool chkmax(T &x, T y) {
  return x < y ? x = y, true : false;
}
template <typename T>
bool chkmin(T &x, T y) {
  return x > y ? x = y, true : false;
}
int readint() {
  int x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
int n, cnta, cntb;
int a[5], b[5], x[5], y[5], now[5], cnt[5], t[5];
pair<int, int> t1[5], t2[5], ans[5];
int getdiv(long long d, bool kp) {
  if (a[1] > a[2]) swap(a[1], a[2]);
  if (b[1] > b[2]) swap(b[1], b[2]);
  int l = 0, r = 1e9, ret = -1, st = 0;
  while (l <= r) {
    int mid = (l + r) / 2;
    int l1 = a[1] - mid, r1 = a[1] + mid;
    int l2 = b[1] - mid, r2 = b[1] + mid;
    int l3 = a[2] - d - mid, r3 = a[2] - d + mid;
    int l4 = b[2] - d - mid, r4 = b[2] - d + mid;
    if (max(max(l1, l2), max(l3, l4)) <= min(min(r1, r2), min(r3, r4))) {
      ret = mid, r = mid - 1;
      if (kp) st = max(max(l1, l2), max(l3, l4));
    } else
      l = mid + 1;
  }
  if (kp) {
    for (int i = 0; i < 4; i++)
      if (x[i] == t[0] && y[i] == a[1]) ans[i] = make_pair(x[i], st);
    for (int i = 0; i < 4; i++)
      if (x[i] == t[0] && y[i] == a[2]) ans[i] = make_pair(x[i], st + d);
    for (int i = 0; i < 4; i++)
      if (x[i] == t[2] && y[i] == b[1]) ans[i] = make_pair(x[i], st);
    for (int i = 0; i < 4; i++)
      if (x[i] == t[2] && y[i] == b[2]) ans[i] = make_pair(x[i], st + d);
  }
  return ret;
}
int solve(int tx, bool kp) {
  for (int i = 0; i < 4; i++) now[i] = (tx >> i) & 1;
  cnt[0] = cnt[1] = 0;
  for (int i = 0; i < 4; i++) cnt[now[i]]++;
  if (cnt[0] == 2 && cnt[1] == 2) {
    int cnt1 = 0, cnt2 = 0;
    for (int i = 0; i < 4; i++) {
      if (!now[i])
        t1[++cnt1] = make_pair(x[i], y[i]);
      else
        t2[++cnt2] = make_pair(x[i], y[i]);
    }
    if (t1[1].first == t1[2].first) {
      for (int i = 0; i < 4; i++) swap(x[i], y[i]);
      for (int i = 1; i <= cnt1; i++) swap(t1[i].first, t1[i].second);
      for (int i = 1; i <= cnt2; i++) swap(t2[i].first, t2[i].second);
      swap(t1, t2);
      for (int i = 0; i < 4; i++) now[i] ^= 1;
      int res = max(
          abs(min(t2[1].first, t2[2].first) - min(t1[1].first, t1[2].first)),
          abs(max(t2[1].first, t2[2].first) - max(t1[1].first, t1[2].first)));
      int tres = 1 << 30, opt = 0,
          ty = t2[1].second + fabs(t1[1].first - t1[2].first);
      if (chkmin(tres, max(abs(t1[1].second - ty), abs(t1[2].second - ty))))
        opt = 1;
      ty = t2[1].second - fabs(t1[1].first - t1[2].first);
      if (chkmin(tres, max(abs(t1[1].second - ty), abs(t1[2].second - ty))))
        opt = 2;
      if (kp) {
        if (opt == 1) {
          ty = t2[1].second + fabs(t1[1].first - t1[2].first);
          for (int i = 0; i < 4; i++)
            if (now[i] && x[i] == min(t2[1].first, t2[2].first))
              ans[i] = make_pair(min(t1[1].first, t1[2].first), y[i]);
          for (int i = 0; i < 4; i++)
            if (now[i] && x[i] == max(t2[1].first, t2[2].first))
              ans[i] = make_pair(max(t1[1].first, t1[2].first), y[i]);
          for (int i = 0; i < 4; i++)
            if (!now[i]) ans[i] = make_pair(x[i], ty);
          for (int i = 0; i < 4; i++)
            if (!now[i]) ans[i] = make_pair(x[i], ty);
        } else {
          ty = t2[1].second - fabs(t1[1].first - t1[2].first);
          for (int i = 0; i < 4; i++)
            if (now[i] && x[i] == min(t2[1].first, t2[2].first))
              ans[i] = make_pair(min(t1[1].first, t1[2].first), y[i]);
          for (int i = 0; i < 4; i++)
            if (now[i] && x[i] == max(t2[1].first, t2[2].first))
              ans[i] = make_pair(max(t1[1].first, t1[2].first), y[i]);
          for (int i = 0; i < 4; i++)
            if (!now[i]) ans[i] = make_pair(x[i], ty);
          for (int i = 0; i < 4; i++)
            if (!now[i]) ans[i] = make_pair(x[i], ty);
        }
        for (int i = 0; i < 4; i++)
          printf("%d %d\n", ans[i].second, ans[i].first);
      }
      for (int i = 0; i < 4; i++) swap(x[i], y[i]);
      return max(tres, res);
    } else if (t2[1].second == t2[2].second) {
      int res = max(
          fabs(min(t2[1].first, t2[2].first) - min(t1[1].first, t1[2].first)),
          fabs(max(t2[1].first, t2[2].first) - max(t1[1].first, t1[2].first)));
      int tres = 1 << 30, opt = 0,
          ty = t2[1].second + fabs(t1[1].first - t1[2].first);
      if (chkmin(tres, max(abs(t1[1].second - ty), abs(t1[2].second - ty))))
        opt = 1;
      ty = t2[1].second - fabs(t1[1].first - t1[2].first);
      if (chkmin(tres, max(abs(t1[1].second - ty), abs(t1[2].second - ty))))
        opt = 2;
      if (kp) {
        if (opt == 1) {
          ty = t2[1].second + fabs(t1[1].first - t1[2].first);
          for (int i = 0; i < 4; i++)
            if (now[i] && x[i] == min(t2[1].first, t2[2].first))
              ans[i] = make_pair(min(t1[1].first, t1[2].first), y[i]);
          for (int i = 0; i < 4; i++)
            if (now[i] && x[i] == max(t2[1].first, t2[2].first))
              ans[i] = make_pair(max(t1[1].first, t1[2].first), y[i]);
          for (int i = 0; i < 4; i++)
            if (!now[i]) ans[i] = make_pair(x[i], ty);
          for (int i = 0; i < 4; i++)
            if (!now[i]) ans[i] = make_pair(x[i], ty);
        } else {
          ty = t2[1].second - fabs(t1[1].first - t1[2].first);
          for (int i = 0; i < 4; i++)
            if (now[i] && x[i] == min(t2[1].first, t2[2].first))
              ans[i] = make_pair(min(t1[1].first, t1[2].first), y[i]);
          for (int i = 0; i < 4; i++)
            if (now[i] && x[i] == max(t2[1].first, t2[2].first))
              ans[i] = make_pair(max(t1[1].first, t1[2].first), y[i]);
          for (int i = 0; i < 4; i++)
            if (!now[i]) ans[i] = make_pair(x[i], ty);
          for (int i = 0; i < 4; i++)
            if (!now[i]) ans[i] = make_pair(x[i], ty);
        }
        for (int i = 0; i < 4; i++)
          printf("%d %d\n", ans[i].first, ans[i].second);
      }
      return max(tres, res);
    }
    if (fabs(t1[2].first - t1[1].first) != fabs(t2[2].second - t2[1].second))
      return 1 << 30;
    int res = 1 << 30, opt = 0;
    if (chkmin(res, max(max(abs(t1[1].second - t2[1].second),
                            abs(t1[2].second - t2[2].second)),
                        max(abs(t2[1].first - t1[2].first),
                            abs(t2[2].first - t1[1].first)))))
      opt = 1;
    if (chkmin(res, max(max(abs(t1[1].second - t2[2].second),
                            abs(t1[2].second - t2[1].second)),
                        max(abs(t2[1].first - t1[1].first),
                            abs(t2[2].first - t1[2].first)))))
      opt = 2;
    if (kp) {
      if (opt == 1) {
        for (int i = 0; i < 4; i++)
          if (make_pair(x[i], y[i]) == t1[1])
            ans[i] = make_pair(t1[1].first, t2[1].second);
        for (int i = 0; i < 4; i++)
          if (make_pair(x[i], y[i]) == t1[2])
            ans[i] = make_pair(t1[2].first, t2[2].second);
        for (int i = 0; i < 4; i++)
          if (make_pair(x[i], y[i]) == t2[1])
            ans[i] = make_pair(t1[2].first, t2[1].second);
        for (int i = 0; i < 4; i++)
          if (make_pair(x[i], y[i]) == t2[2])
            ans[i] = make_pair(t1[1].first, t2[2].second);
      } else {
        for (int i = 0; i < 4; i++)
          if (make_pair(x[i], y[i]) == t1[1])
            ans[i] = make_pair(t1[1].first, t2[2].second);
        for (int i = 0; i < 4; i++)
          if (make_pair(x[i], y[i]) == t1[2])
            ans[i] = make_pair(t1[2].first, t2[1].second);
        for (int i = 0; i < 4; i++)
          if (make_pair(x[i], y[i]) == t2[1])
            ans[i] = make_pair(t1[1].first, t2[1].second);
        for (int i = 0; i < 4; i++)
          if (make_pair(x[i], y[i]) == t2[2])
            ans[i] = make_pair(t1[2].first, t2[2].second);
      }
      for (int i = 0; i < 4; i++)
        printf("%d %d\n", ans[i].first, ans[i].second);
    }
    return res;
  } else if (cnt[0] > cnt[1]) {
    if (cnt[0] == 4) {
      for (int i = 0; i < 4; i++) t[i] = x[i];
      sort(t, t + 4);
      if (t[0] != t[1] || t[2] != t[3] || t[1] == t[2]) return 1 << 30;
      cnta = cntb = 0;
      for (int i = 0; i < 4; i++) {
        if (x[i] == t[1])
          a[++cnta] = y[i];
        else
          b[++cntb] = y[i];
      }
      int ret = getdiv(fabs(t[2] - t[0]), kp);
      if (kp) {
        for (int i = 0; i < 4; i++)
          printf("%d %d\n", ans[i].first, ans[i].second);
      }
      return ret;
    } else {
      int tcnt = 0, pl = 0, ply = 0;
      for (int i = 0; i < 4; i++) {
        if (!now[i])
          t[tcnt++] = x[i];
        else
          pl = x[i], ply = y[i];
      }
      sort(t, t + 3);
      if (t[0] != t[1] && t[1] != t[2]) return 1 << 30;
      if (t[0] != t[1]) swap(t[0], t[2]);
      cnta = cntb = 0;
      for (int i = 0; i < 4; i++) {
        if (now[i]) continue;
        if (x[i] == t[0])
          a[++cnta] = y[i];
        else
          b[++cntb] = y[i];
      }
      int res = fabs(pl - t[2]), tres = 1 << 30;
      int ty = ply - fabs(t[0] - t[2]), opt = 0;
      if (chkmin(tres, max(abs(b[1] - ty),
                           min(max(abs(a[1] - ply), abs(a[2] - ty)),
                               max(abs(a[2] - ply), abs(a[1] - ty))))))
        opt = 1;
      ty = ply + fabs(t[0] - t[2]);
      if (chkmin(tres, max(abs(b[1] - ty),
                           min(max(abs(a[1] - ply), abs(a[2] - ty)),
                               max(abs(a[2] - ply), abs(a[1] - ty))))))
        opt = 2;
      if (kp) {
        if (opt == 1) {
          ty = ply - fabs(t[0] - t[2]);
          if (max(abs(a[1] - ply), abs(a[2] - ty)) <
              max(abs(a[2] - ply), abs(a[1] - ty))) {
            for (int i = 0; i < 4; i++)
              if (now[i]) ans[i] = make_pair(t[2], y[i]);
            for (int i = 0; i < 4; i++) {
              if (now[i]) continue;
              if (x[i] == t[2])
                ans[i] = make_pair(x[i], ty);
              else if (x[i] == t[0] && y[i] == a[1])
                ans[i] = make_pair(x[i], ply);
              else if (x[i] == t[0] && y[i] == a[2])
                ans[i] = make_pair(x[i], ty);
            }
          } else {
            for (int i = 0; i < 4; i++)
              if (now[i]) ans[i] = make_pair(t[2], y[i]);
            for (int i = 0; i < 4; i++) {
              if (now[i]) continue;
              if (x[i] == t[2])
                ans[i] = make_pair(x[i], ty);
              else if (x[i] == t[0] && y[i] == a[1])
                ans[i] = make_pair(x[i], ty);
              else if (x[i] == t[0] && y[i] == a[2])
                ans[i] = make_pair(x[i], ply);
            }
          }
        } else {
          ty = ply + fabs(t[0] - t[2]);
          if (max(abs(a[1] - ply), abs(a[2] - ty)) <
              max(abs(a[2] - ply), abs(a[1] - ty))) {
            for (int i = 0; i < 4; i++)
              if (now[i]) ans[i] = make_pair(t[2], y[i]);
            for (int i = 0; i < 4; i++) {
              if (now[i]) continue;
              if (x[i] == t[2])
                ans[i] = make_pair(x[i], ty);
              else if (x[i] == t[0] && y[i] == a[1])
                ans[i] = make_pair(x[i], ply);
              else if (x[i] == t[0] && y[i] == a[2])
                ans[i] = make_pair(x[i], ty);
            }
          } else {
            for (int i = 0; i < 4; i++)
              if (now[i]) ans[i] = make_pair(t[2], y[i]);
            for (int i = 0; i < 4; i++) {
              if (now[i]) continue;
              if (x[i] == t[2])
                ans[i] = make_pair(x[i], ty);
              else if (x[i] == t[0] && y[i] == a[1])
                ans[i] = make_pair(x[i], ty);
              else if (x[i] == t[0] && y[i] == a[2])
                ans[i] = make_pair(x[i], ply);
            }
          }
        }
        for (int i = 0; i < 4; i++)
          printf("%d %d\n", ans[i].first, ans[i].second);
      }
      return max(tres, res);
    }
  } else {
    for (int i = 0; i < 4; i++) now[i] ^= 1;
    swap(cnt[0], cnt[1]);
    for (int i = 0; i < 4; i++) swap(x[i], y[i]);
    if (cnt[0] == 4) {
      for (int i = 0; i < 4; i++) t[i] = x[i];
      sort(t, t + 4);
      if (t[0] != t[1] || t[2] != t[3] || t[1] == t[2]) {
        for (int i = 0; i < 4; i++) swap(x[i], y[i]);
        return 1 << 30;
      }
      cnta = cntb = 0;
      for (int i = 0; i < 4; i++) {
        if (x[i] == t[1])
          a[++cnta] = y[i];
        else
          b[++cntb] = y[i];
      }
      int ret = getdiv(fabs(t[2] - t[0]), kp);
      for (int i = 0; i < 4; i++) swap(x[i], y[i]);
      if (kp) {
        for (int i = 0; i < 4; i++)
          printf("%d %d\n", ans[i].second, ans[i].first);
      }
      return ret;
    } else {
      int tcnt = 0, pl = 0, ply = 0;
      for (int i = 0; i < 4; i++) {
        if (!now[i])
          t[tcnt++] = x[i];
        else
          pl = x[i], ply = y[i];
      }
      sort(t, t + 3);
      if (t[0] != t[1] && t[1] != t[2]) {
        for (int i = 0; i < 4; i++) swap(x[i], y[i]);
        return 1 << 30;
      }
      if (t[0] != t[1]) swap(t[0], t[2]);
      cnta = cntb = 0;
      for (int i = 0; i < 4; i++) {
        if (now[i]) continue;
        if (x[i] == t[0])
          a[++cnta] = y[i];
        else
          b[++cntb] = y[i];
      }
      int res = fabs(pl - t[2]), tres = 1 << 30;
      int ty = ply - fabs(t[0] - t[2]), opt = 0;
      if (chkmin(tres, max(abs(b[1] - ty),
                           min(max(abs(a[1] - ply), abs(a[2] - ty)),
                               max(abs(a[2] - ply), abs(a[1] - ty))))))
        opt = 1;
      ty = ply + fabs(t[0] - t[2]);
      if (chkmin(tres, max(abs(b[1] - ty),
                           min(max(abs(a[1] - ply), abs(a[2] - ty)),
                               max(abs(a[2] - ply), abs(a[1] - ty))))))
        opt = 2;
      if (kp) {
        if (opt == 1) {
          ty = ply - fabs(t[0] - t[2]);
          if (max(abs(a[1] - ply), abs(a[2] - ty)) <
              max(abs(a[2] - ply), abs(a[1] - ty))) {
            for (int i = 0; i < 4; i++)
              if (now[i]) ans[i] = make_pair(t[2], y[i]);
            for (int i = 0; i < 4; i++) {
              if (now[i]) continue;
              if (x[i] == t[2])
                ans[i] = make_pair(x[i], ty);
              else if (x[i] == t[0] && y[i] == a[1])
                ans[i] = make_pair(x[i], ply);
              else if (x[i] == t[0] && y[i] == a[2])
                ans[i] = make_pair(x[i], ty);
            }
          } else {
            for (int i = 0; i < 4; i++)
              if (now[i]) ans[i] = make_pair(t[2], y[i]);
            for (int i = 0; i < 4; i++) {
              if (now[i]) continue;
              if (x[i] == t[2])
                ans[i] = make_pair(x[i], ty);
              else if (x[i] == t[0] && y[i] == a[1])
                ans[i] = make_pair(x[i], ty);
              else if (x[i] == t[0] && y[i] == a[2])
                ans[i] = make_pair(x[i], ply);
            }
          }
        } else {
          ty = ply + fabs(t[0] - t[2]);
          if (max(abs(a[1] - ply), abs(a[2] - ty)) <
              max(abs(a[2] - ply), abs(a[1] - ty))) {
            for (int i = 0; i < 4; i++)
              if (now[i]) ans[i] = make_pair(t[2], y[i]);
            for (int i = 0; i < 4; i++) {
              if (now[i]) continue;
              if (x[i] == t[2])
                ans[i] = make_pair(x[i], ty);
              else if (x[i] == t[0] && y[i] == a[1])
                ans[i] = make_pair(x[i], ply);
              else if (x[i] == t[0] && y[i] == a[2])
                ans[i] = make_pair(x[i], ty);
            }
          } else {
            for (int i = 0; i < 4; i++)
              if (now[i]) ans[i] = make_pair(t[2], y[i]);
            for (int i = 0; i < 4; i++) {
              if (now[i]) continue;
              if (x[i] == t[2])
                ans[i] = make_pair(x[i], ty);
              else if (x[i] == t[0] && y[i] == a[1])
                ans[i] = make_pair(x[i], ty);
              else if (x[i] == t[0] && y[i] == a[2])
                ans[i] = make_pair(x[i], ply);
            }
          }
        }
        for (int i = 0; i < 4; i++)
          printf("%d %d\n", ans[i].second, ans[i].first);
      }
      for (int i = 0; i < 4; i++) swap(x[i], y[i]);
      return max(tres, res);
    }
  }
}
int main() {
  int T = readint();
  while (T--) {
    for (int i = 0; i < 4; i++) x[i] = readint(), y[i] = readint();
    int cho = 0, res = 1 << 30;
    for (int i = 0; i < (1 << 4); i++)
      if (chkmin(res, solve(i, 0))) cho = i;
    if (res == (1 << 30))
      printf("-1\n");
    else {
      printf("%d\n", res);
      solve(cho, 1);
    }
  }
  return 0;
}

```