Problem: You're given the centers of three equal sides of a strictly convex tetragon. Your task is to restore the initial tetragon.

Input

The first input line contains one number T — amount of tests (1 ≤ T ≤ 5·104). Each of the following T lines contains numbers x1, y1, x2, y2, x3, y3 — coordinates of different points that are the centers of three equal sides (non-negative integer numbers, not exceeding 10).

Output

For each test output two lines. If the required tetragon exists, output in the first line YES, in the second line — four pairs of numbers — coordinates of the polygon's vertices in clockwise or counter-clockwise order. Don't forget, please, that the tetragon should be strictly convex, i.e. no 3 of its points lie on one line. Output numbers with 9 characters after a decimal point.

If the required tetragon doen't exist, output NO in the first line, and leave the second line empty.

Examples

Input

3
1 1 2 2 3 3
0 1 1 0 2 2
9 3 7 9 9 8


Output

NO

YES
3.5 1.5 0.5 2.5 -0.5 -0.5 2.5 0.5
NO

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
const double eps = 1e-12;
struct point {
  double x, y;
};
int t;
double cross(point a, point b, point c) {
  b.x -= a.x;
  b.y -= a.y;
  c.x -= a.x;
  c.y -= a.y;
  return b.x * c.y - b.y * c.x;
}
bool check(point a, point b, point c) {
  double kx1 = 2.0 * (b.x - a.x), ky1 = 2.0 * (b.y - a.y),
         s1 = b.x * b.x + b.y * b.y - a.x * a.x - a.y * a.y;
  double kx2 = -2.0 * (b.x - c.x), ky2 = -2.0 * (b.y - c.y),
         s2 = b.x * b.x + b.y * b.y - c.x * c.x - c.y * c.y -
              4.0 * b.x * (b.x - c.x) - 4.0 * b.y * (b.y - c.y);
  double kx = kx1 * ky2 - kx2 * ky1, s = s1 * ky2 - s2 * ky1;
  if (kx > -eps && kx < eps) return false;
  double x = s / kx, y;
  if (ky1 <= -eps || ky1 >= eps)
    y = (s1 - kx1 * x) / ky1;
  else if (ky2 <= -eps || ky2 >= eps)
    y = (s2 - kx2 * x) / ky2;
  else
    return false;
  point va, vb, vc, vd;
  va.x = x;
  va.y = y;
  vb.x = b.x + b.x - va.x;
  vb.y = b.y + b.y - va.y;
  vc.x = c.x + c.x - vb.x;
  vc.y = c.y + c.y - vb.y;
  vd.x = a.x + a.x - va.x;
  vd.y = a.y + a.y - va.y;
  double ca = cross(va, vb, vc), cb = cross(vb, vc, vd), cc = cross(vc, vd, va),
         cd = cross(vd, va, vb);
  if ((ca > 0 && cb > 0 && cc > 0 && cd > 0) ||
      (ca < 0 && cb < 0 && cc < 0 && cd < 0)) {
    puts("YES");
    printf("%.9lf %.9lf %.9lf %.9lf %.9lf %.9lf %.9lf %.9lf\n", va.x, va.y,
           vb.x, vb.y, vc.x, vc.y, vd.x, vd.y);
    return true;
  }
  return false;
}
point a, b, c;
int main() {
  scanf("%d", &t);
  while (t--) {
    scanf("%lf%lf%lf%lf%lf%lf", &a.x, &a.y, &b.x, &b.y, &c.x, &c.y);
    if (!check(a, b, c) && !check(b, a, c) && !check(a, c, b)) {
      puts("NO");
      puts("");
    }
  }
  return 0;
}