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>
const double ZERO = 1e-12;
using namespace std;
int compute(double, double, double, double, double, double);
int check(double, double, double, double, double, double, double, double);
int main(int argc, char *argv[]) {
  int n;
  double x1, y1, x2, y2, x3, y3;
  cin >> n;
  while (n--) {
    cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
    if (compute(x1, y1, x2, y2, x3, y3) == 0 &&
        compute(x2, y2, x3, y3, x1, y1) == 0 &&
        compute(x3, y3, x1, y1, x2, y2) == 0)
      cout << "NO" << endl;
  }
  return EXIT_SUCCESS;
}
int compute(double x1, double y1, double x2, double y2, double x3, double y3) {
  double xA, yA, xB, yB, xC, yC, xD, yD;
  double A = x1 + x3 - 2 * x2, B = y1 + y3 - 2 * y2, C = (x1 + 2 * x2 - x3) / 2,
         D = (y1 + 2 * y2 - y3) / 2, M = (x2 - x1), N = (y2 - y1),
         P = (x1 * x1 - x2 * x2 + y1 * y1 - y2 * y2) / 2, E = -(A * C + B * D);
  if (A * N - B * M == 0)
    return 0;
  else {
    yD = (M * E - A * P) / (A * N - B * M);
    xD = (N * E - B * P) / (-A * N + B * M);
    xA = 2 * x1 - xD;
    yA = 2 * y1 - yD;
    xC = 2 * x2 - xD;
    yC = 2 * y2 - yD;
    xB = 2 * x3 - xC;
    yB = 2 * y3 - yC;
    if (check(xA, yA, xB, yB, xC, yC, xD, yD)) {
      cout << "YES" << endl;
      printf("%.9lf %.9lf %.9lf %.9lf %.9lf %.9lf %.9lf %.9lf\n", xA, yA, xB,
             yB, xC, yC, xD, yD);
      return 1;
    }
  }
  return 0;
}
int check(double xA, double yA, double xB, double yB, double xC, double yC,
          double xD, double yD) {
  int flag = 0;
  if (((yA - yB) * (xC - xA) - (xA - xB) * (yC - yA)) *
          ((yA - yB) * (xD - xA) - (xA - xB) * (yD - yA)) <=
      ZERO)
    flag++;
  if (((yB - yC) * (xD - xB) - (xB - xC) * (yD - yB)) *
          ((yB - yC) * (xA - xB) - (xB - xC) * (yA - yB)) <=
      ZERO)
    flag++;
  if (((yC - yD) * (xA - xC) - (xC - xD) * (yA - yC)) *
          ((yC - yD) * (xB - xC) - (xC - xD) * (yB - yC)) <=
      ZERO)
    flag++;
  if (((yD - yA) * (xB - xD) - (xD - xA) * (yB - yD)) *
          ((yD - yA) * (xC - xD) - (xD - xA) * (yC - yD)) <=
      ZERO)
    flag++;
  if (flag == 0)
    return 1;
  else
    return 0;
}