F. Turtles
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are playing games with turtles! In your pocket you find two arrays of integers $$$a$$$, $$$b$$$, of lengths $$$N$$$ and $$$M$$$, satisfying $$$a_i \lt a_{i+2}$$$ and $$$b_i \lt b_{i+2}$$$.

There are two turtles, one red and one blue, which are both at the same position, but are facing opposite directions.

The red turtle, for each $$$i$$$ from 1 to $$$N$$$, will move $$$a_i$$$ steps, then turn right 90 degrees.

The blue turtle, for each $$$i$$$ from 1 to $$$M$$$, will move $$$b_i$$$ steps, then turn right 90 degrees.

Once they finish, they will stop.

Output whether their paths will intersect.

Note that a turtle stopping on the other's path would still count as an intersection.

Input

The first line consists of an integer $$$t$$$ ($$$1 \le t \le 100$$$), the number of test cases.

The first line of each test case consists of two integers $$$N$$$ and $$$M$$$ ($$$1 \le N,M \le 10^5$$$), the number of steps the red turtle will take, and the number of steps the blue turtle will take, respectively.

The second line of each test case consists of $$$a_1,a_2,...,a_N$$$ ($$$1 \le a_i \le 10^9$$$), describing the red turtle's path.

The third line of each test case consists of $$$b_1,b_2,...,b_M$$$ ($$$1 \le b_i \le 10^9$$$), describing the blue turtle's path.

The sum of $$$N$$$ and the sum of $$$M$$$ over all $$$t$$$ test cases doesn't exceed $$$10^5$$$.

—

Tests in subtasks are numbered $$$1 - 20$$$ with samples skipped. Each test is worth $$$\frac{100}{20} = 5$$$ points.

Tests $$$1-2$$$ satisfy $$$N,M,a_i,b_i \le 100$$$.

Tests $$$3-4$$$ satisfy $$$N,M \le 1000$$$.

Tests $$$5-20$$$ satisfy no additional constraints.

Output

For each test case, output "YES" if the paths of the turtles will intersect; otherwise, output "NO." Note that the checker is case-sensitive, so outputs such as "yEs" will not be accepted.

Example
Input
2
6 6
1 2 3 4 5 6
1 1 3 4 6 6
6 3
1 2 3 4 5 6
1 3 5
Output
NO
YES
Note

Visualization for test cases 1 and 2:

Test Case 1
Test Case 2

—

Problem Idea: alexlikemath007

Problem Preparation: Buzzy2

Occurrences: Novice F, Advanced B