Problem C
Can Tho Expressway

The governor of Can Tho is planning to build a new expressway in this city. The expressway will connect Can Tho and Ho Chi Minh City, bringing prosperity to the region.

Picture of Can Tho by Liftold, cc-by-sa.

Naturally, the expressway cannot intersect with Can Tho’s famous tourist destination, ‘Cai Rang Floating Market’, which can not be moved. Your task is to check whether the new Can Tho expressway intersects with ‘Cai Rang Floating Market’.

More formally, the new Can Tho expressway can be represented with two parallel lines $a \cdot x + b \cdot y = c_1$ and $a \cdot x + b \cdot y = c_2$ — the area between the two parallel lines is the expressway. ‘Cai Rang Floating Market’ can be approximately represented by a convex polygon with at most $6$ vertices. You need to check whether the new expressway and ‘Cai Rang Floating Market’ have positive common area.

Input

The first line of the input contains a single integer $t$ $(1 \leq t \leq 10\, 000)$ — the number of test cases. $t$ test cases follow, each test case is described as below:

• The first line contains $4$ integers $a$, $b$, $c_1$, and $c_2$ $(-100 \le a, b, c_1, c_2 \le 100, a^2 + b^2 > 0, c_1 \neq c_2)$.

• The second line contains an integer $k$ $(3 \le k \le 6)$ — the number of vertices of the convex polygon representing ‘Cai Rang Floating Market’, followed by $2 \cdot k$ integers $x_1 \; y_1 \; x_2 \; y_2 \; \ldots \; x_ k \; y_ k$ $(-10^4 \le x_ i, y_ i \le 10^4)$ — the coordinates of the vertices of the polygon. The vertices are listed in either clockwise or counter-clockwise order. In each polygon, no two vertices have the same coordinates, and no three consecutive vertices are collinear.

Output

For each test case, print a single line containing ‘YES’ if the new expressway and ‘Cai Rang Floating Market’ have positive common area, and ‘NO’ otherwise.

Explanation of the sample input

In the below figures, ‘Cai Rang Floating Market’ is denoted by a blue polygon. The new expressway is shaded in grey. The intersection is represented in red.

The following figure shows the first test case:

The following figure shows the second test case:

2
0 1 0 1
6 2 2 1 3 1 4 2 5 3 4 3 3
0 1 0 1
6 2 -1 1 0 1 1 2 2 3 1 3 0

NO
YES