← 返回题目列表

Codeforces · 516/E

E. 德拉齐尔和他快乐的朋友

中文机器翻译题面 查看原题

Drazil 有很多朋友。他们有的人高兴,有的人不高兴。德拉齐尔想让他所有的朋友都变得快乐。所以他发明了以下计划。

他的朋友中有n个男孩和m个女孩。让我们分别从 0 到 n-1 和 0 到 m-1 编号。第i天,Drazil邀请第$$(i \bmod n)$$个男孩和第$$(i \bmod m)$$个女孩一起吃饭(由于Drazil是程序员,i从0开始)。如果两个人其中一个人幸福,另一个人也会幸福。否则的话,那两个人就留在他们的状态了。一个人一旦变得快乐(或者本来就是快乐的),他就会永远快乐。

Drazil 想知道哪一天他所有的朋友都会变得快乐,或者确定他们是否根本不会变得快乐。

输入

第一行包含两个整数 n 和 m (1 ≤ n, m ≤ 109)。

第二行包含整数 b (0 ≤ b ≤ min(n, 105)),表示 Drazil 的朋友中快乐男孩的数量,然后跟随 b 个不同的整数 x1, x2, ..., xb (0 ≤ xi < n),表示快乐男孩的索引列表。

第三行包含整数g(0 ≤ g ≤ min(m, 105)),表示Drazil的朋友中快乐女孩的数量,然后跟随g个不同的整数y1, y2, ... , yg (0 ≤ yj < m),表示快乐女孩的索引列表。

保证他的朋友中至少有一个人不开心。

输出

打印Drazil的所有朋友都变得快乐的第一天的数字。如果这一天根本不会到来,则打印 -1。

示例

输入 #1

2 3
0
1 0

输出 #1

4

输入 #2

2 4
1 0
1 2

输出 #2

-1

输入 #3

2 3
1 0
1 1

输出 #3

2

输入#4

99999 100000
2 514 415
2 50216 61205

输出#4

4970100515

注意

通过 $$i \bmod k$$ 我们定义 i 除以 k 的余数。

在第一个示例案例中:

- 第 0 天,Drazil 邀请了第 0 个男孩和第 0 个女孩。因为第 0 个女孩一开始是快乐的,所以第 0 个男孩在这一天变得快乐。
- 在第一天,Drazil 邀请了第一个男孩和第一个女孩。他们俩都很不高兴,所以这一天没有任何改变。
- 第二天,Drazil 邀请了第 0 个男孩和第 2 个女孩。因为第 0 个男孩已经很高兴,所以他让第 2 个女孩在这一天变得快乐。
- 第三天,Drazil 邀请了第 1 个男孩和第 0 个女孩。第 0 个女孩很高兴,所以她让第 1 个男孩也很高兴。
- 第 4 天,Drazil 邀请了第 0 个男孩和第 1 个女孩。第 0 个男孩很高兴,所以他让第 1 个女孩也高兴。所以,所有的朋友这一刻都变得幸福起来。