問題文

2つの数列 $X,Y$ がある. 数列 $X$ は長さが $N$ の 数列 $A$ を無限に繰り返しており, 数列 $Y$ は長さ $M$ の数列 $B$ を無限に繰り返す.

より厳密には, 数列 $X$ は数列 $A$ を用いて, $X=(A_1,A_2,\dots, A_N,A_1,\dots,A_N,A_1,\dots,A_N,\dots)$ のように構成されている. $Y$ についても同様である.

このとき, $X_i=Y_i$ を満たす正の整数 $i$ が存在すれば, そのような整数のうち, 最小のものを出力せよ. もし, 存在しなければ, その旨を報告せよ.

なお, 数列の初項は第 $1$ 項とする. また, 数列 $Z$ と正の整数 $r$ に対して, $Z_r$ で数列 $Z$ の第 $r$ 項を表すとする.

制約

• $1 \leq N,M \leq 5000$
• $1 \leq A_i,B_i \leq 10^4$
• 入力は全て整数である.

入力

入力は以下の形式で標準入力から与えられる.

$N$ $M$
$A_1$ $\dots$ $A_N$
$B_1$ $\dots$ $B_M$

出力

$X_i=Y_i$ を満たす正の整数 $i$ が存在すれば, そのような整数のうち最小のものを, 存在しなければ, $-1$ を出力せよ. 最後に改行を忘れないこと.

サンプル

2 3
1 2
2 3 3

4

4 1
3 9 1 5
4

-1

10 7
3 4 10 8 19 1 12 39 2 5
8 100 3 38 29 4 11

31