У выдающегося миллиардера Цая есть весьма специфическая одержимость: он чувствует себя комфортно только тогда, когда его ступни твёрдо стоят на стороне или вершине замощения — то есть на границе некоторой напольной плитки. Недавно он приобрёл коллекцию одинаковых элитных треугольных напольных плиток. Он планирует использовать эти плитки, чтобы выложить пол в длинном прямом коридоре своего нового особняка.
Коридор представляет собой бесконечную полосу на двумерной плоскости. Чтобы дизайн соответствовал его высочайшим стандартам, Цай установил строгое правило укладки: каждая треугольная плитка должна располагаться так, чтобы перекрывать всю ширину коридора, касаясь обеих параллельных граничных прямых. Это создаёт непрерывное однорядное замощение (тесселяцию) полосы. Одна из этих плиток должна в точности совпадать с его любимым эталонным треугольником, а все остальные плитки должны быть конгруэнтны ему.
Сейчас Цай стоит в фиксированной точке коридора. Он измотан после долгого дня работ по терраформированию и, откровенно говоря, вообще не собирается сдвигаться с места. Он хочет, чтобы плитки автоматически разрослись по полу, начиная от его эталонного треугольника, при условии, что итоговый узор будет подчиняться его правилам. Разумеется, успехом считается только тот случай, когда сторона или вершина плиток совпадёт с его текущим положением!
Ваша задача — определить, можно ли выложить коридор плиткой так, чтобы текущее положение Цая, точка $D$, лежало в точности на стороне или вершине замощения, содержащего $\triangle ABC$. Границы коридора определяются как две единственные параллельные прямые $l_1$ и $l_2$ такие, что $l_1$ проходит через $A$ и $B$, а $l_2$ проходит через $C$. Замощение полосы, образованной $(l_1, l_2)$, — это покрытие всей полосы конгруэнтными копиями треугольника $\triangle ABC$ (допускаются параллельный перенос, поворот и отражение) без наложений и зазоров.
Иллюстрация первых двух тестовых примеров.
Входные данные
Входные данные состоят из нескольких наборов. Первая строка входных данных содержит целое число $T$ ($1 \le T \le 10^3$), обозначающее количество наборов входных данных. Для каждого набора:
Первая строка содержит два целых числа $x_a$ и $y_a$ ($-100 \le x_a, y_a \le 100$) — координаты точки $A$.
Вторая строка содержит два целых числа $x_b$ и $y_b$ ($-100 \le x_b, y_b \le 100$) — координаты точки $B$.
Третья строка содержит два целых числа $x_c$ и $y_c$ ($-100 \le x_c, y_c \le 100$) — координаты точки $C$.
Четвёртая строка содержит две дроби $x_{d1}/x_{d2}$ и $y_{d1}/y_{d2}$, где $x_{d1}, x_{d2}, y_{d1}, y_{d2}$ — целые числа, удовлетворяющие условиям $-10^7 < x_{d1}, y_{d1} < 10^7$ и $0 < x_{d2}, y_{d2} < 10^7$, представляющие координаты точки $D$.
Гарантируется, что точки $A$, $B$ и $C$ образуют невырожденный треугольник.
Выходные данные
Для каждого набора входных данных выведите в отдельной строке "Yes", если существует корректное замощение, при котором точка $D$ лежит на стороне или вершине хотя бы одного треугольника в узоре. В противном случае выведите "No".
Примеры
Входные данные 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
Выходные данные 1
Yes No Yes No