Cai, l'eccezionale miliardario, ha un'ossessione molto particolare: si sente a suo agio solo quando i suoi piedi sono ben piantati su un lato o un vertice della piastrellatura — cioè sul bordo di qualche piastrella del pavimento. Di recente ha acquistato una collezione di identiche piastrelle triangolari di alta gamma. Ha intenzione di utilizzare queste piastrelle per pavimentare un lungo corridoio rettilineo nella sua nuova villa.
Il corridoio è una striscia infinita su un piano bidimensionale. Per garantire che il design soddisfi i suoi standard supremi, Cai ha imposto una rigida regola di piastrellatura: ogni singola piastrella triangolare deve essere posizionata in modo da coprire l'intera larghezza del corridoio, toccando entrambe le linee di confine parallele. Ciò crea una tassellazione continua a fila singola della striscia. Una di queste piastrelle deve corrispondere esattamente al suo triangolo di riferimento preferito e tutte le altre piastrelle devono essere congruenti ad esso.
Cai si trova attualmente in una posizione fissa nel corridoio. È esausto dopo una lunga giornata di lavori di terraformazione e, francamente, non ha alcuna intenzione di muoversi. Vuole che le piastrelle si estendano automaticamente sul pavimento a partire dal suo triangolo di riferimento, purché il motivo risultante segua le sue regole. Naturalmente, sarà un successo solo se un lato o un vertice delle piastrelle coincide con la sua posizione attuale!
Il tuo compito è determinare se è possibile piastrellare il corridoio in modo che la posizione attuale di Cai, il punto $D$, giaccia esattamente su un lato o un vertice della tassellazione contenente $\triangle ABC$. I confini del corridoio sono definiti come le due uniche rette parallele $l_1$ e $l_2$ tali che $l_1$ passa per $A$ e $B$, e $l_2$ passa per $C$. Una tassellazione della striscia formata da $(l_1, l_2)$ è una piastrellatura dell'intera striscia mediante copie congruenti del triangolo $\triangle ABC$ (consentendo traslazione, rotazione e riflessione), senza sovrapposizioni e senza spazi vuoti.
Illustrazione dei primi due casi di test di esempio.
Input
Ci sono più casi di test. La prima riga dell'input contiene un intero $T$ ($1 \le T \le 10^3$) che indica il numero di casi di test. Per ogni caso di test:
La prima riga contiene due interi $x_a$ e $y_a$ ($-100 \le x_a, y_a \le 100$), le coordinate del punto $A$.
La seconda riga contiene due interi $x_b$ e $y_b$ ($-100 \le x_b, y_b \le 100$), le coordinate del punto $B$.
La terza riga contiene due interi $x_c$ e $y_c$ ($-100 \le x_c, y_c \le 100$), le coordinate del punto $C$.
La quarta riga contiene due frazioni $x_{d1}/x_{d2}$ e $y_{d1}/y_{d2}$, dove $x_{d1}, x_{d2}, y_{d1}, y_{d2}$ sono interi che soddisfano $-10^7 < x_{d1}, y_{d1} < 10^7$ e $0 < x_{d2}, y_{d2} < 10^7$, che rappresentano le coordinate del punto $D$.
È garantito che $A$, $B$ e $C$ formino un triangolo non degenere.
Output
Per ogni caso di test, stampa "Yes" su una riga se esiste una tassellazione valida tale che il punto $D$ giaccia su un lato o un vertice di almeno un triangolo nel motivo. Altrimenti, stampa "No".
Esempi
Input 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
Output 1
Yes No Yes No