Infinite Game

Time limit5sMemory limit128 MB

Summary

Given sets A and B of positive steps taken alternately right and left, decide whether every integer can be reached.

Level: Medium6 of 10
Topics: Number theory, Dynamic programming, Math, Game theory
Solved: No attempts yet

Problem

Sanggeun stands at integer $0$ on the number line. He moves using two finite sets of positive integers, $A$ and $B$ .

Each move follows these rules:

On every odd-numbered move he chooses a number from set $A$ and steps that many units to the right.
On every even-numbered move he chooses a number from set $B$ and steps that many units to the left.

So the first move uses $A$ , the second uses $B$ , the third uses $A$ again, and so on, alternating between the two sets. On each move he may freely choose any number from the corresponding set.

Write a program that decides whether Sanggeun can reach every integer $x$ , both positive and negative.

Input

The first line contains the number of test cases $t$ ( $1 \le t \le 500$ ).

Each test case begins with a line containing two integers $n$ and $m$ separated by a space ( $1 \le n, m \le 10\,000$ ), where $n$ is the size of set $A$ and $m$ is the size of set $B$ . The next $n$ lines each contain one element of $A$ , and the following $m$ lines each contain one element of $B$ . Every element is an integer between $1$ and $10^9$ , inclusive.

Output

For each test case, print YES on its own line if Sanggeun can reach every integer, and NO otherwise.

Examples4

Example 1
Input
```
2
1 1
2
2
2 2
1
2
1
2
```
Expected output
```
NO
YES
```
Example 2
Input
```
1
2 2
2
3
2
3
```
Expected output
```
YES
```
Example 3
Input
```
1
2 2
2
4
2
4
```
Expected output
```
NO
```
Example 4
Input
```
1
2 2
1
3
1
3
```
Expected output
```
YES
```