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 个女孩也高兴。所以,所有的朋友这一刻都变得幸福起来。