#include <bits/stdc++.h>
clock_t ti = clock();
namespace STD {
static char buf[100000], *p1 = buf, *p2 = buf;
inline char Get() {
  return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
             ? EOF
             : *p1++;
}
inline long long Read() {
  long long ans = 0, fl = 1;
  char ch = getchar();
  for (; ch < '0' || ch > '9'; ch = getchar())
    if (ch == '-') fl = -1;
  for (; '0' <= ch && ch <= '9'; ch = getchar())
    ans = (ans << 3) + (ans << 1) + (ch ^ '0');
  return ans * fl;
}
inline long long Fast_pow(long long a, long long b, long long p) {
  long long ret = 1;
  while (b != 0) {
    if ((b & 1) == 1) ret = (ret * a) % p;
    a = (a * a) % p, b >>= 1;
  }
  return ret;
}
inline void Print(long long x) {
  if (x < 0) x = -x, putchar('-');
  if (x >= 10) Print(x / 10);
  putchar((x % 10) | '0');
}
inline void Print(long long x, char s) {
  Print(x);
  putchar(s);
}
inline void File_in() { freopen("a.in", "r", stdin); }
inline void File_out() { freopen("a.out", "w", stdout); }
inline void Check_time() {
  printf("Runtime : %g s\n", (clock() - ti) / 1000.00);
}
using namespace std;
}  // namespace STD
using namespace STD;
const double eps = 1e-6;
const double Pi = acos(-1);
long long x[4][3], y[4][3];
inline double Get_len(long long a1, long long b1, long long a2, long long b2) {
  return sqrt((a1 - a2) * (a1 - a2) + (b1 - b2) * (b1 - b2));
}
inline bool Get_gradient(long long a1, long long b1, long long a2, long long b2,
                         long long a3, long long b3) {
  long long A = b2 - b1;
  long long B = a1 - a2;
  long long C = a2 * b1 - a1 * b2;
  double r1 = Get_len(a1, b1, a3, b3);
  double r2 = Get_len(a2, b2, a3, b3);
  double r3 = Get_len(a1, b1, a2, b2);
  return fabs(A * a3 + B * b3 + C) < eps && fabs(r1 + r2 - r3) < eps;
}
inline bool Get_angle(long long a1, long long b1, long long a2, long long b2,
                      long long a3, long long b3) {
  double r1 = Get_len(a1, b1, a2, b2);
  double r2 = Get_len(a3, b3, a1, b1);
  double r3 = Get_len(a2, b2, a3, b3);
  if (r1 == 0 || r2 == 0) return false;
  return r1 * r1 + r2 * r2 > r3 * r3;
}
inline bool Check(long long _a, long long _b, long long _c, long long a,
                  long long b, long long c) {
  if (x[_a][a] != x[_b][b] || y[_a][a] != y[_b][b]) return false;
  bool pd1 = Get_gradient(x[_a][a], y[_a][a], x[_a][3 - a], y[_a][3 - a],
                          x[_c][c], y[_c][c]);
  bool pd2 = Get_gradient(x[_b][b], y[_b][b], x[_b][3 - b], y[_b][3 - b],
                          x[_c][3 - c], y[_c][3 - c]);
  if (!pd1 || !pd2) return false;
  double r1 = Get_len(x[_a][a], y[_a][a], x[_c][c], y[_c][c]);
  double r2 = Get_len(x[_c][c], y[_c][c], x[_a][3 - a], y[_a][3 - a]);
  double r3 = Get_len(x[_b][b], y[_b][b], x[_c][3 - c], y[_c][3 - c]);
  double r4 = Get_len(x[_c][3 - c], y[_c][3 - c], x[_b][3 - b], y[_b][3 - b]);
  if (((r1) < (r2) ? (r1) : (r2)) * 4 < ((r1) > (r2) ? (r1) : (r2)) ||
      ((r3) < (r4) ? (r3) : (r4)) * 4 < ((r3) > (r4) ? (r3) : (r4)))
    return false;
  return Get_angle(x[_a][a], y[_a][a], x[_a][3 - a], y[_a][3 - a], x[_b][3 - b],
                   y[_b][3 - b]);
}
int main() {
  int test = Read();
  while (test--) {
    bool pd = false;
    for (int i = 1; i <= 3; i++)
      for (int j = 1; j <= 2; j++) {
        x[i][j] = Read();
        y[i][j] = Read();
      }
    for (int _i = 1; _i <= 3; _i++)
      for (int _j = 1; _j <= 3; _j++)
        for (int _k = 1; _k <= 3; _k++)
          for (int i = 1; i <= 2; i++)
            for (int j = 1; j <= 2; j++)
              for (int k = 1; k <= 2; k++)
                if (_i != _j && _i != _k && _j != _k &&
                    Check(_i, _j, _k, i, j, k) == true) {
                  pd = true;
                  goto Finish;
                }
  Finish:
    printf("%s\n", pd ? "YES" : "NO");
  }
  return 0;
}

### Prompt

Please provide a cpp coded solution to the problem described below:

Little Petya learns how to write. The teacher gave pupils the task to write the letter A on the sheet of paper. It is required to check whether Petya really had written the letter A.

You are given three segments on the plane. They form the letter A if the following conditions hold:

  * Two segments have common endpoint (lets call these segments first and second), while the third segment connects two points on the different segments. 
  * The angle between the first and the second segments is greater than 0 and do not exceed 90 degrees. 
  * The third segment divides each of the first two segments in proportion not less than 1 / 4 (i.e. the ratio of the length of the shortest part to the length of the longest part is not less than 1 / 4). 

Input

The first line contains one integer t (1 ≤ t ≤ 10000) — the number of test cases to solve. Each case consists of three lines. Each of these three lines contains four space-separated integers — coordinates of the endpoints of one of the segments. All coordinates do not exceed 108 by absolute value. All segments have positive length.

Output

Output one line for each test case. Print «YES» (without quotes), if the segments form the letter A and «NO» otherwise.

Examples

Input

3
4 4 6 0
4 1 5 2
4 0 4 4
0 0 0 6
0 6 2 -4
1 1 0 1
0 0 0 5
0 5 2 -1
1 2 0 1


Output

YES
NO
YES

### Response

```cpp
#include <bits/stdc++.h>
clock_t ti = clock();
namespace STD {
static char buf[100000], *p1 = buf, *p2 = buf;
inline char Get() {
  return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2)
             ? EOF
             : *p1++;
}
inline long long Read() {
  long long ans = 0, fl = 1;
  char ch = getchar();
  for (; ch < '0' || ch > '9'; ch = getchar())
    if (ch == '-') fl = -1;
  for (; '0' <= ch && ch <= '9'; ch = getchar())
    ans = (ans << 3) + (ans << 1) + (ch ^ '0');
  return ans * fl;
}
inline long long Fast_pow(long long a, long long b, long long p) {
  long long ret = 1;
  while (b != 0) {
    if ((b & 1) == 1) ret = (ret * a) % p;
    a = (a * a) % p, b >>= 1;
  }
  return ret;
}
inline void Print(long long x) {
  if (x < 0) x = -x, putchar('-');
  if (x >= 10) Print(x / 10);
  putchar((x % 10) | '0');
}
inline void Print(long long x, char s) {
  Print(x);
  putchar(s);
}
inline void File_in() { freopen("a.in", "r", stdin); }
inline void File_out() { freopen("a.out", "w", stdout); }
inline void Check_time() {
  printf("Runtime : %g s\n", (clock() - ti) / 1000.00);
}
using namespace std;
}  // namespace STD
using namespace STD;
const double eps = 1e-6;
const double Pi = acos(-1);
long long x[4][3], y[4][3];
inline double Get_len(long long a1, long long b1, long long a2, long long b2) {
  return sqrt((a1 - a2) * (a1 - a2) + (b1 - b2) * (b1 - b2));
}
inline bool Get_gradient(long long a1, long long b1, long long a2, long long b2,
                         long long a3, long long b3) {
  long long A = b2 - b1;
  long long B = a1 - a2;
  long long C = a2 * b1 - a1 * b2;
  double r1 = Get_len(a1, b1, a3, b3);
  double r2 = Get_len(a2, b2, a3, b3);
  double r3 = Get_len(a1, b1, a2, b2);
  return fabs(A * a3 + B * b3 + C) < eps && fabs(r1 + r2 - r3) < eps;
}
inline bool Get_angle(long long a1, long long b1, long long a2, long long b2,
                      long long a3, long long b3) {
  double r1 = Get_len(a1, b1, a2, b2);
  double r2 = Get_len(a3, b3, a1, b1);
  double r3 = Get_len(a2, b2, a3, b3);
  if (r1 == 0 || r2 == 0) return false;
  return r1 * r1 + r2 * r2 > r3 * r3;
}
inline bool Check(long long _a, long long _b, long long _c, long long a,
                  long long b, long long c) {
  if (x[_a][a] != x[_b][b] || y[_a][a] != y[_b][b]) return false;
  bool pd1 = Get_gradient(x[_a][a], y[_a][a], x[_a][3 - a], y[_a][3 - a],
                          x[_c][c], y[_c][c]);
  bool pd2 = Get_gradient(x[_b][b], y[_b][b], x[_b][3 - b], y[_b][3 - b],
                          x[_c][3 - c], y[_c][3 - c]);
  if (!pd1 || !pd2) return false;
  double r1 = Get_len(x[_a][a], y[_a][a], x[_c][c], y[_c][c]);
  double r2 = Get_len(x[_c][c], y[_c][c], x[_a][3 - a], y[_a][3 - a]);
  double r3 = Get_len(x[_b][b], y[_b][b], x[_c][3 - c], y[_c][3 - c]);
  double r4 = Get_len(x[_c][3 - c], y[_c][3 - c], x[_b][3 - b], y[_b][3 - b]);
  if (((r1) < (r2) ? (r1) : (r2)) * 4 < ((r1) > (r2) ? (r1) : (r2)) ||
      ((r3) < (r4) ? (r3) : (r4)) * 4 < ((r3) > (r4) ? (r3) : (r4)))
    return false;
  return Get_angle(x[_a][a], y[_a][a], x[_a][3 - a], y[_a][3 - a], x[_b][3 - b],
                   y[_b][3 - b]);
}
int main() {
  int test = Read();
  while (test--) {
    bool pd = false;
    for (int i = 1; i <= 3; i++)
      for (int j = 1; j <= 2; j++) {
        x[i][j] = Read();
        y[i][j] = Read();
      }
    for (int _i = 1; _i <= 3; _i++)
      for (int _j = 1; _j <= 3; _j++)
        for (int _k = 1; _k <= 3; _k++)
          for (int i = 1; i <= 2; i++)
            for (int j = 1; j <= 2; j++)
              for (int k = 1; k <= 2; k++)
                if (_i != _j && _i != _k && _j != _k &&
                    Check(_i, _j, _k, i, j, k) == true) {
                  pd = true;
                  goto Finish;
                }
  Finish:
    printf("%s\n", pd ? "YES" : "NO");
  }
  return 0;
}

```