Cai, der herausragende Milliardär, hat eine ganz besondere Obsession: Er fühlt sich nur wohl, wenn seine Füße fest auf einer Kante oder Ecke des Fliesenmusters stehen — das heißt auf dem Rand einer Bodenfliese. Kürzlich erwarb er eine Kollektion identischer, hochwertiger dreieckiger Bodenfliesen. Er plant, mit diesen Fliesen einen langen, geraden Korridor in seiner neuen Villa zu fliesen.
Der Korridor ist ein unendlicher Streifen in einer zweidimensionalen Ebene. Um sicherzustellen, dass das Design seinen höchsten Ansprüchen genügt, hat Cai eine strenge Fliesenregel diktiert: Jede einzelne dreieckige Fliese muss so platziert werden, dass sie die gesamte Breite des Korridors überspannt und beide parallelen Begrenzungslinien berührt. Dies erzeugt eine durchgehende, einreihige Parkettierung (Tessellation) des Streifens. Eine dieser Fliesen muss genau mit seinem bevorzugten Referenzdreieck übereinstimmen, und alle anderen Fliesen müssen dazu kongruent sein.
Cai steht derzeit an einer festen Position im Flur. Er ist nach einem langen Tag voller Terraforming-Arbeiten erschöpft und wird sich, offen gesagt, überhaupt nicht bewegen. Er möchte, dass die Fliesen ausgehend von seinem Referenzdreieck automatisch über den Boden wachsen, solange das entstehende Muster seinen Regeln folgt. Natürlich ist es nur dann ein Erfolg, wenn eine Kante oder Ecke der Fliesen mit seiner aktuellen Position zusammenfällt!
Ihre Aufgabe ist es zu bestimmen, ob es möglich ist, den Korridor so zu fliesen, dass Cais aktuelle Position, Punkt $D$, genau auf einer Kante oder einer Ecke der Parkettierung liegt, die $\triangle ABC$ enthält. Die Grenzen des Korridors sind definiert als die zwei eindeutigen parallelen Geraden $l_1$ und $l_2$, sodass $l_1$ durch $A$ und $B$ verläuft und $l_2$ durch $C$ verläuft. Eine Parkettierung des durch $(l_1, l_2)$ gebildeten Streifens ist eine Überdeckung des gesamten Streifens mit kongruenten Kopien des Dreiecks $\triangle ABC$ (wobei Verschiebung, Drehung und Spiegelung erlaubt sind) ohne Überlappungen und ohne Lücken.
Veranschaulichung der ersten beiden Beispiel-Testfälle.
Eingabe
Es gibt mehrere Testfälle. Die erste Zeile der Eingabe enthält eine ganze Zahl $T$ ($1 \le T \le 10^3$), die die Anzahl der Testfälle angibt. Für jeden Testfall gilt:
Die erste Zeile enthält zwei ganze Zahlen $x_a$ und $y_a$ ($-100 \le x_a, y_a \le 100$), die Koordinaten von Punkt $A$.
Die zweite Zeile enthält zwei ganze Zahlen $x_b$ und $y_b$ ($-100 \le x_b, y_b \le 100$), die Koordinaten von Punkt $B$.
Die dritte Zeile enthält zwei ganze Zahlen $x_c$ und $y_c$ ($-100 \le x_c, y_c \le 100$), die Koordinaten von Punkt $C$.
Die vierte Zeile enthält zwei Brüche $x_{d1}/x_{d2}$ und $y_{d1}/y_{d2}$, wobei $x_{d1}, x_{d2}, y_{d1}, y_{d2}$ ganze Zahlen sind, die $-10^7 < x_{d1}, y_{d1} < 10^7$ und $0 < x_{d2}, y_{d2} < 10^7$ erfüllen und die Koordinaten von Punkt $D$ darstellen.
Es ist garantiert, dass $A$, $B$ und $C$ ein nicht-entartetes Dreieck bilden.
Ausgabe
Geben Sie für jeden Testfall in einer Zeile "Yes" aus, wenn eine gültige Parkettierung existiert, sodass Punkt $D$ auf einer Kante oder einer Ecke von mindestens einem Dreieck im Muster liegt. Andernfalls geben Sie "No" aus.
Beispiele
Eingabe 1
4 -2 1 0 0 0 2 2/1 0/1 -2 1 0 0 0 2 1/1 0/1 0 1 -2 1 0 2 1/2 7/4 0 1 -2 1 0 2 -3/2 3/4
Ausgabe 1
Yes No Yes No