#include <bits/stdc++.h>
using namespace std;
const char eof = -123;
void printBits(unsigned int x, int end = 32, int start = 0) {
  for (int i = end - 1; i >= start; i--)
    if (x & (1 << i))
      cout << 1 << " ";
    else
      cout << 0 << " ";
}
int readInt() {
  int x;
  if (scanf("%d", &x) != 1) return eof;
  return x;
}
char readChar() {
  char c;
  if (scanf("%c", &c) != 1) return eof;
  return c;
}
long long int readLL() {
  long long int x;
  if (cin >> x) return x;
  return eof;
}
double readDouble() {
  double f;
  if (scanf("%lf", &f) == 1) return f;
  return eof;
}
template <class T>
class Point;
template <class T>
class Vector;
template <class T>
class Line;
template <class T>
class Segment;
template <class T>
class Line {
 public:
  Point<T> P;
  Vector<T> V;
  Line() {}
  Line(Point<T> A, Point<T> B) {
    P = A;
    V = B - A;
  }
  pair<int, Point<T> > intersect(Line L) {
    if (V.isZeroVector()) {
      if (L.containsPoint(P)) return make_pair(1, P);
      return make_pair(0, P);
    }
    if (L.V.isZeroVector()) {
      if (containsPoint(L.P)) return make_pair(1, L.P);
      return make_pair(0, P);
    }
    if (V.isParallel(L.V)) {
      if (L.containsPoint(P)) return make_pair(2, P);
      return make_pair(0, P);
    }
    T numerator = L.V.crossProduct(L.P - this->P);
    T denominator = L.V.crossProduct(this->V);
    if (denominator < 0) {
      numerator = -numerator;
      denominator = -denominator;
    }
    return make_pair(1, P + V * make_pair(numerator, denominator));
  }
  bool containsPoint(const Point<T> A) {
    Vector<T> D = A - P;
    if (D.isZeroVector()) return true;
    if (V.isZeroVector()) return false;
    return V.isParallel(D);
  }
  Line<T>& read(istream& in = cin) {
    P.read(in);
    V = Point<T>().read() - P;
    return *this;
  }
  Line<T>& write(ostream& out = cout) {
    out << "L(";
    P.write();
    out << ", ";
    (V + P).write();
    out << ")";
    return *this;
  }
};
template <class T>
class Segment {
 public:
  Point<T> P;
  Vector<T> V;
  Point<T> Q;
  Segment() {}
  Segment(Point<T> A, Point<T> B) {
    P = A;
    V = B - A;
    Q = P + V;
  }
  pair<int, Point<T> > intersect(const Segment& S) {
    Line<T> thisLine = Line<T>(P, Q);
    Line<T> segLine = Line<T>(S.P, S.Q);
    pair<int, Point<T> > C = thisLine.intersect(segLine);
    if (C.first == 0) return C;
    if (C.first == 1) {
      if (containsPoint(C.second) && S.containsPoint(C.second))
        return make_pair(1, C.second);
      return make_pair(0, C.second);
    }
    T one, two, three, four;
    if (V.x == 0) {
      one = P.y, two = Q.y, three = S.P.y, four = S.Q.y;
    } else {
      one = P.x, two = Q.x, three = S.P.x, four = S.Q.x;
    }
    bool firstSwap = true, secondSwap = true;
    if (isGreater(one, two)) {
      swap(one, two);
      firstSwap = false;
    }
    if (isGreater(three, four)) {
      swap(three, four);
      secondSwap = false;
    }
    if (isGreater(three, two)) return make_pair(0, P);
    if (isLesser(four, one)) return make_pair(0, P);
    if (isEqual(four, one)) return make_pair(1, firstSwap ? P : Q);
    if (isEqual(three, two)) return make_pair(1, firstSwap ? Q : P);
    if (!isLesser(four, two)) return make_pair(2, firstSwap ? Q : P);
    return make_pair(2, secondSwap ? S.Q : S.P);
  }
  bool containsPoint(const Point<T>& A) const {
    Vector<T> D = A - P;
    if (D.isZeroVector()) return true;
    if (V.isZeroVector()) return false;
    if (!V.isParallel(D)) return false;
    T vd = V.dotProduct(D);
    T dd = D.dotProduct(D);
    return (vd >= dd);
  }
  pair<T, T> getCoordinate(const Point<T>& A) {
    Vector<T> D = A - P;
    if (D.isZeroVector()) return make_pair(0, 1);
    if (V.isZeroVector()) return make_pair(0, 0);
    if (!V.isParallel(D)) return make_pair(0, 0);
    T vd = V.dotProduct(D);
    T dd = D.dotProduct(D);
    if (vd < 0) return make_pair(-dd, -vd);
    return make_pair(dd, vd);
  }
  Segment<T>& read(istream& in = cin) {
    P.read(in);
    Q.read(in);
    V = Q - P;
    return *this;
  }
  Segment<T>& write(ostream& out = cout) {
    out << "S(";
    P.write();
    out << ", ";
    (V + P).write();
    out << ")";
    return *this;
  }

 private:
  bool isGreater(T a, T b) { return a > b; }
  bool isEqual(T a, T b) { return a == b; }
  bool isLesser(T a, T b) { return !isGreater(a, b) && !isEqual(a, b); }
  bool isGreater(pair<T, T> A, pair<T, T> B) {
    return isGreater(A.first * B.second, A.second * B.first);
  }
  bool isEqual(pair<T, T> A, pair<T, T> B) {
    return isEqual(A.first * B.second, A.second * B.first);
  }
  bool isLesser(pair<T, T> A, pair<T, T> B) {
    return isLesser(A.first * B.second, A.second * B.first);
  }
};
template <class T>
class Vector {
 public:
  T x, y;
  double eps;
  Vector() {}
  Vector(T _x, T _y) {
    this->x = _x;
    this->y = _y;
    eps = 1e-10;
  }
  Vector<T> operator-(const Vector<T>& V) {
    return Vector<T>(x - V.x, y - V.y);
  }
  Vector<T> operator+(const Vector<T>& V) {
    return Vector<T>(x + V.x, y + V.y);
  }
  Vector<T> operator*(T r) { return Vector<T>(x * r, y * r); }
  Vector<T> operator*(pair<T, T> fraction) {
    return Vector<T>(x * (fraction.first / fraction.second),
                     y * (fraction.first / fraction.second));
  }
  Point<T> operator+(const Point<T>& P) const {
    return Point<T>(x + P.x, y + P.y);
  }
  T isZeroVector() const { return norm() <= eps * eps; }
  T dotProduct(const Vector& V) const { return x * V.x + y * V.y; }
  T crossProduct(const Vector& V) const { return x * V.y - y * V.x; }
  T norm() const { return x * x + y * y; }
  bool isParallel(const Vector& v) const { return crossProduct(v) == 0; }
  bool isPerpendicular(const Vector& v) const { return dotProduct(v) == 0; }
  bool isPerpendicular(Vector v) const { return dotProduct(v) == 0; }
  bool isLongerThan(const Vector& v) const { return norm() > v.norm(); }
  bool isNoShorterThan(const Vector& v) const { return norm() >= v.norm(); }
  void rotate(double alpha, bool counterClockWise) {
    if (!counterClockWise) alpha = -alpha;
    doRotateCCW(alpha, x, y);
  }
  vector<T> getRotated(double alpha, bool counterClockWise) {
    if (!counterClockWise) alpha = -alpha;
    T newX, newY;
    doRotateCCW(alpha, newX, newY);
    return Vector<T>(newX, newY);
  }
  Vector<T>& read(istream& in = cin) {
    in >> x >> y;
    return *this;
  }
  Vector<T>& write(ostream& out = cout) {
    out << "V(" << x << ", " << y;
    out << ")";
    return *this;
  }

 private:
  void doRotateCCW(double alpha, T& x, T& y) {
    T newX = x * cos(alpha) - y * sin(alpha);
    T newY = x * sin(alpha) + y * cos(alpha);
    x = newX;
    y = newY;
  }
};
template <class T>
class Point {
 public:
  T x, y;
  Point() {}
  Point(T _x, T _y) {
    this->x = _x;
    this->y = _y;
  }
  Vector<T> operator-(const Point& p) const {
    return Vector<T>(x - p.x, y - p.y);
  }
  Point<T> operator+(const Vector<T>& v) const {
    return Point<T>(x + v.x, y + v.y);
  }
  Point<T>& read(istream& in = cin) {
    in >> x >> y;
    return *this;
  }
  Point<T>& write(ostream& out = cout) {
    out << "P(" << x << "," << y << ")";
    return *this;
  }
};
Segment<long long int> S[3];
bool bad(pair<long long int, long long int> P) {
  return P.first * 5 < P.second || P.first * 5 > 4 * P.second;
}
bool checkA(vector<int>& perm) {
  int i = perm[0], j = perm[1], k = perm[2];
  Segment<long long int> A = S[i], B = S[j], C = S[k];
  pair<int, Point<long long int> > D = A.intersect(B);
  if (D.first != 1) return false;
  Point<long long int> E = D.second;
  Vector<long long int> p1 = A.P - B.P, p2 = A.P - B.Q, p3 = A.Q - B.P,
                        p4 = A.Q - B.Q;
  if (p1.isZeroVector()) {
  } else if (p2.isZeroVector()) {
    B = Segment<long long int>(B.Q, B.P);
  } else if (p3.isZeroVector()) {
    A = Segment<long long int>(A.Q, A.P);
  } else if (p4.isZeroVector()) {
    A = Segment<long long int>(A.Q, A.P);
    B = Segment<long long int>(B.Q, B.P);
  } else
    return false;
  if (A.V.isParallel(B.V)) return false;
  if (A.V.dotProduct(B.V) < 0) return false;
  if (!A.containsPoint(C.P)) C = Segment<long long int>(C.Q, C.P);
  if (!A.containsPoint(C.P) || !B.containsPoint(C.Q)) return false;
  pair<long long int, long long int> C1 = A.getCoordinate(C.P);
  if (bad(C1)) return false;
  pair<long long int, long long int> C2 = B.getCoordinate(C.Q);
  if (bad(C2)) return false;
  return true;
}
int main() {
  int cases = readInt();
  while (cases--) {
    for (int i = 0; i < (3); ++i) S[i].read();
    vector<int> v;
    for (int i = 0; i < (3); ++i) v.push_back(i);
    bool good = false;
    do {
      if (checkA(v)) {
        good = true;
        break;
      }
    } while (next_permutation(v.begin(), v.end()));
    if (good)
      cout << "YES\n";
    else
      cout << "NO\n";
  }
}

### Prompt

Develop a solution in CPP 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>
using namespace std;
const char eof = -123;
void printBits(unsigned int x, int end = 32, int start = 0) {
  for (int i = end - 1; i >= start; i--)
    if (x & (1 << i))
      cout << 1 << " ";
    else
      cout << 0 << " ";
}
int readInt() {
  int x;
  if (scanf("%d", &x) != 1) return eof;
  return x;
}
char readChar() {
  char c;
  if (scanf("%c", &c) != 1) return eof;
  return c;
}
long long int readLL() {
  long long int x;
  if (cin >> x) return x;
  return eof;
}
double readDouble() {
  double f;
  if (scanf("%lf", &f) == 1) return f;
  return eof;
}
template <class T>
class Point;
template <class T>
class Vector;
template <class T>
class Line;
template <class T>
class Segment;
template <class T>
class Line {
 public:
  Point<T> P;
  Vector<T> V;
  Line() {}
  Line(Point<T> A, Point<T> B) {
    P = A;
    V = B - A;
  }
  pair<int, Point<T> > intersect(Line L) {
    if (V.isZeroVector()) {
      if (L.containsPoint(P)) return make_pair(1, P);
      return make_pair(0, P);
    }
    if (L.V.isZeroVector()) {
      if (containsPoint(L.P)) return make_pair(1, L.P);
      return make_pair(0, P);
    }
    if (V.isParallel(L.V)) {
      if (L.containsPoint(P)) return make_pair(2, P);
      return make_pair(0, P);
    }
    T numerator = L.V.crossProduct(L.P - this->P);
    T denominator = L.V.crossProduct(this->V);
    if (denominator < 0) {
      numerator = -numerator;
      denominator = -denominator;
    }
    return make_pair(1, P + V * make_pair(numerator, denominator));
  }
  bool containsPoint(const Point<T> A) {
    Vector<T> D = A - P;
    if (D.isZeroVector()) return true;
    if (V.isZeroVector()) return false;
    return V.isParallel(D);
  }
  Line<T>& read(istream& in = cin) {
    P.read(in);
    V = Point<T>().read() - P;
    return *this;
  }
  Line<T>& write(ostream& out = cout) {
    out << "L(";
    P.write();
    out << ", ";
    (V + P).write();
    out << ")";
    return *this;
  }
};
template <class T>
class Segment {
 public:
  Point<T> P;
  Vector<T> V;
  Point<T> Q;
  Segment() {}
  Segment(Point<T> A, Point<T> B) {
    P = A;
    V = B - A;
    Q = P + V;
  }
  pair<int, Point<T> > intersect(const Segment& S) {
    Line<T> thisLine = Line<T>(P, Q);
    Line<T> segLine = Line<T>(S.P, S.Q);
    pair<int, Point<T> > C = thisLine.intersect(segLine);
    if (C.first == 0) return C;
    if (C.first == 1) {
      if (containsPoint(C.second) && S.containsPoint(C.second))
        return make_pair(1, C.second);
      return make_pair(0, C.second);
    }
    T one, two, three, four;
    if (V.x == 0) {
      one = P.y, two = Q.y, three = S.P.y, four = S.Q.y;
    } else {
      one = P.x, two = Q.x, three = S.P.x, four = S.Q.x;
    }
    bool firstSwap = true, secondSwap = true;
    if (isGreater(one, two)) {
      swap(one, two);
      firstSwap = false;
    }
    if (isGreater(three, four)) {
      swap(three, four);
      secondSwap = false;
    }
    if (isGreater(three, two)) return make_pair(0, P);
    if (isLesser(four, one)) return make_pair(0, P);
    if (isEqual(four, one)) return make_pair(1, firstSwap ? P : Q);
    if (isEqual(three, two)) return make_pair(1, firstSwap ? Q : P);
    if (!isLesser(four, two)) return make_pair(2, firstSwap ? Q : P);
    return make_pair(2, secondSwap ? S.Q : S.P);
  }
  bool containsPoint(const Point<T>& A) const {
    Vector<T> D = A - P;
    if (D.isZeroVector()) return true;
    if (V.isZeroVector()) return false;
    if (!V.isParallel(D)) return false;
    T vd = V.dotProduct(D);
    T dd = D.dotProduct(D);
    return (vd >= dd);
  }
  pair<T, T> getCoordinate(const Point<T>& A) {
    Vector<T> D = A - P;
    if (D.isZeroVector()) return make_pair(0, 1);
    if (V.isZeroVector()) return make_pair(0, 0);
    if (!V.isParallel(D)) return make_pair(0, 0);
    T vd = V.dotProduct(D);
    T dd = D.dotProduct(D);
    if (vd < 0) return make_pair(-dd, -vd);
    return make_pair(dd, vd);
  }
  Segment<T>& read(istream& in = cin) {
    P.read(in);
    Q.read(in);
    V = Q - P;
    return *this;
  }
  Segment<T>& write(ostream& out = cout) {
    out << "S(";
    P.write();
    out << ", ";
    (V + P).write();
    out << ")";
    return *this;
  }

 private:
  bool isGreater(T a, T b) { return a > b; }
  bool isEqual(T a, T b) { return a == b; }
  bool isLesser(T a, T b) { return !isGreater(a, b) && !isEqual(a, b); }
  bool isGreater(pair<T, T> A, pair<T, T> B) {
    return isGreater(A.first * B.second, A.second * B.first);
  }
  bool isEqual(pair<T, T> A, pair<T, T> B) {
    return isEqual(A.first * B.second, A.second * B.first);
  }
  bool isLesser(pair<T, T> A, pair<T, T> B) {
    return isLesser(A.first * B.second, A.second * B.first);
  }
};
template <class T>
class Vector {
 public:
  T x, y;
  double eps;
  Vector() {}
  Vector(T _x, T _y) {
    this->x = _x;
    this->y = _y;
    eps = 1e-10;
  }
  Vector<T> operator-(const Vector<T>& V) {
    return Vector<T>(x - V.x, y - V.y);
  }
  Vector<T> operator+(const Vector<T>& V) {
    return Vector<T>(x + V.x, y + V.y);
  }
  Vector<T> operator*(T r) { return Vector<T>(x * r, y * r); }
  Vector<T> operator*(pair<T, T> fraction) {
    return Vector<T>(x * (fraction.first / fraction.second),
                     y * (fraction.first / fraction.second));
  }
  Point<T> operator+(const Point<T>& P) const {
    return Point<T>(x + P.x, y + P.y);
  }
  T isZeroVector() const { return norm() <= eps * eps; }
  T dotProduct(const Vector& V) const { return x * V.x + y * V.y; }
  T crossProduct(const Vector& V) const { return x * V.y - y * V.x; }
  T norm() const { return x * x + y * y; }
  bool isParallel(const Vector& v) const { return crossProduct(v) == 0; }
  bool isPerpendicular(const Vector& v) const { return dotProduct(v) == 0; }
  bool isPerpendicular(Vector v) const { return dotProduct(v) == 0; }
  bool isLongerThan(const Vector& v) const { return norm() > v.norm(); }
  bool isNoShorterThan(const Vector& v) const { return norm() >= v.norm(); }
  void rotate(double alpha, bool counterClockWise) {
    if (!counterClockWise) alpha = -alpha;
    doRotateCCW(alpha, x, y);
  }
  vector<T> getRotated(double alpha, bool counterClockWise) {
    if (!counterClockWise) alpha = -alpha;
    T newX, newY;
    doRotateCCW(alpha, newX, newY);
    return Vector<T>(newX, newY);
  }
  Vector<T>& read(istream& in = cin) {
    in >> x >> y;
    return *this;
  }
  Vector<T>& write(ostream& out = cout) {
    out << "V(" << x << ", " << y;
    out << ")";
    return *this;
  }

 private:
  void doRotateCCW(double alpha, T& x, T& y) {
    T newX = x * cos(alpha) - y * sin(alpha);
    T newY = x * sin(alpha) + y * cos(alpha);
    x = newX;
    y = newY;
  }
};
template <class T>
class Point {
 public:
  T x, y;
  Point() {}
  Point(T _x, T _y) {
    this->x = _x;
    this->y = _y;
  }
  Vector<T> operator-(const Point& p) const {
    return Vector<T>(x - p.x, y - p.y);
  }
  Point<T> operator+(const Vector<T>& v) const {
    return Point<T>(x + v.x, y + v.y);
  }
  Point<T>& read(istream& in = cin) {
    in >> x >> y;
    return *this;
  }
  Point<T>& write(ostream& out = cout) {
    out << "P(" << x << "," << y << ")";
    return *this;
  }
};
Segment<long long int> S[3];
bool bad(pair<long long int, long long int> P) {
  return P.first * 5 < P.second || P.first * 5 > 4 * P.second;
}
bool checkA(vector<int>& perm) {
  int i = perm[0], j = perm[1], k = perm[2];
  Segment<long long int> A = S[i], B = S[j], C = S[k];
  pair<int, Point<long long int> > D = A.intersect(B);
  if (D.first != 1) return false;
  Point<long long int> E = D.second;
  Vector<long long int> p1 = A.P - B.P, p2 = A.P - B.Q, p3 = A.Q - B.P,
                        p4 = A.Q - B.Q;
  if (p1.isZeroVector()) {
  } else if (p2.isZeroVector()) {
    B = Segment<long long int>(B.Q, B.P);
  } else if (p3.isZeroVector()) {
    A = Segment<long long int>(A.Q, A.P);
  } else if (p4.isZeroVector()) {
    A = Segment<long long int>(A.Q, A.P);
    B = Segment<long long int>(B.Q, B.P);
  } else
    return false;
  if (A.V.isParallel(B.V)) return false;
  if (A.V.dotProduct(B.V) < 0) return false;
  if (!A.containsPoint(C.P)) C = Segment<long long int>(C.Q, C.P);
  if (!A.containsPoint(C.P) || !B.containsPoint(C.Q)) return false;
  pair<long long int, long long int> C1 = A.getCoordinate(C.P);
  if (bad(C1)) return false;
  pair<long long int, long long int> C2 = B.getCoordinate(C.Q);
  if (bad(C2)) return false;
  return true;
}
int main() {
  int cases = readInt();
  while (cases--) {
    for (int i = 0; i < (3); ++i) S[i].read();
    vector<int> v;
    for (int i = 0; i < (3); ++i) v.push_back(i);
    bool good = false;
    do {
      if (checkA(v)) {
        good = true;
        break;
      }
    } while (next_permutation(v.begin(), v.end()));
    if (good)
      cout << "YES\n";
    else
      cout << "NO\n";
  }
}

```