printРабочее место участника

printЗадачи

1428. Infinite Game

Ограничения: время – 12s/24s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

Krzysztof had a little too much to drink tonight and is now walking around aimlessly. He has two sets of moves `A`, `B`. Each of `A`,`B` is a finite subset of the positive integers. Krzysztof starts off standing at 0, and at each step he either takes a step to the right by an integer in `A`, or takes a step to the left by an integer in `B`. In odd-numbered steps his move must be from `A`, and in even-numbered steps his move must be from `B` (the first step he makes is considered step number 1). Is it true that for every integer `x` (both the positives and the negatives), Krzysztof can eventually reach `x`?
Input
The first line contains a positive integer `t`, the number of test cases (`1\ ≤\ t\ ≤\ 500`). `t` sets of lines then follow. Each set of lines start with a line with two space-separated integers `n`, `m` (`1\ ≤\ n,m\ ≤\ 10000`), denoting the sizes of `A` and `B`, respectively. `n` lines then follow listing the elements of `A`, then `m` lines follow listing the elements of `B`. Each element of `A`,`B` will be an integer between 1 and `10^9`, inclusive.
Output
For each test case output "YES" if Krzysztof can eventually reach all integers; else output "NO". The word you output should be followed by a newline.

Sample Input

2
1 1
2
2
2 2
1
2
1
2

Sample Output

NO
YES
Source: MIT Programming Team Contest 1, 2008
loading