Universal Cup Judging System

Universal Cup

時間限制: 2.0 s 記憶體限制: 2048 MB 總分: 100 难度: [顯示] 可 Hack ✓
统计

Cai, the outstanding billionaire, has a very particular obsession: he only feels comfortable when his feet are planted firmly on an edge or vertex of the tiling — that is, on the boundary of some floor tile. Recently, he acquired a collection of identical, high-end triangular floor tiles. He plans to use these tiles to tile a long, straight corridor in his new mansion.

The corridor is an infinite strip on a two-dimensional plane. To ensure the design meets his supreme standards, Cai has dictated a strict tiling rule: every single triangular tile must be placed such that it spans the entire width of the corridor, touching both parallel boundary lines. This creates a continuous, single-row tessellation of the strip. One of these tiles must exactly match his favorite reference triangle, and all other tiles must be congruent to it.

Cai is currently standing at a fixed location in the hallway. He is exhausted after a long day of terraforming work and, quite frankly, will not move at all. He wants the tiles to grow automatically across the floor starting from his reference triangle, as long as the resulting pattern follows his rules. Of course, it is only a success if an edge or vertex of the tiles coincides with his current position!

Your task is to determine if it is possible to tile the corridor such that Cai's current position, point $D$, lies exactly on an edge or a vertex of the tessellation containing $\triangle ABC$. The corridor's boundaries are defined as the two unique parallel lines $l_1$ and $l_2$ such that $l_1$ passes through $A$ and $B$, and $l_2$ passes through $C$. A tessellation of the strip formed by $(l_1, l_2)$ is a tiling of the entire strip using congruent copies of triangle $\triangle ABC$ (allowing translation, rotation, and reflection), with no overlaps and no gaps.

problem_16328_12fab1fef4e720550593a9e1ba8664f5.png

Illustration of the first two sample test cases.

Input

There are multiple test cases. The first line of the input contains an integer $T$ ($1 \le T \le 10^3$) indicating the number of test cases. For each test case:

The first line contains two integers $x_a$ and $y_a$ ($-100 \le x_a, y_a \le 100$), the coordinates of point $A$.

The second line contains two integers $x_b$ and $y_b$ ($-100 \le x_b, y_b \le 100$), the coordinates of point $B$.

The third line contains two integers $x_c$ and $y_c$ ($-100 \le x_c, y_c \le 100$), the coordinates of point $C$.

The fourth line contains two fractions $x_{d1}/x_{d2}$ and $y_{d1}/y_{d2}$, where $x_{d1}, x_{d2}, y_{d1}, y_{d2}$ are integers satisfying $-10^7 < x_{d1}, y_{d1} < 10^7$ and $0 < x_{d2}, y_{d2} < 10^7$, representing the coordinates of point $D$.

It is guaranteed that $A$, $B$, and $C$ form a non-degenerate triangle.

Output

For each test case, output "Yes" in a line if there exists a valid tessellation such that point $D$ lies on an edge or a vertex of at least one triangle in the pattern. Otherwise, output "No".

Examples

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

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.