問題文

長さ $N$ の文字列 $S$ と長さ $M$ の文字列 $T$ が与えられます。 どちらの文字列も、英小文字からなります。

文字列 $X$ は、以下の条件をすべて満たす時、よい文字列と呼ばれます。

• $X$ の長さを $L$ とした時、$L$ は $N$ と $M$ のどちらでも割り切れる
• $X$ の $1,\\ \\frac{L}{N}+1,\\ 2 \\times \\frac{L}{N}+1,\\ ...\\ (N-1)\\times\\frac{L}{N}+1$ 番目の文字を並べ替えることなく連結すると $S$ になる
• $X$ の $1,\\ \\frac{L}{M}+1,\\ 2 \\times \\frac{L}{M}+1,\\ ...\\ (M-1)\\times\\frac{L}{M}+1$ 番目の文字を並べ替えることなく連結すると $T$ になる

よい文字列が存在するか判定し、存在するならば、その中で最短のものの長さを求めてください。

制約

• $1 \\leq N,M \\leq 10^5$
• $S$, $T$ は英小文字からなる。
• $|S|=N$
• $|T|=M$

入力

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

$N$ $M$ $S$ $T$

出力

よい文字列が存在しないならば、-1 と出力せよ。 存在するならば、その中で最短のものの長さを出力せよ。

入力例 1

3 2
acp
ae

出力例 1

6

例えば、accept という文字列はよい文字列です。 これより短いよい文字列は存在しないので、答えは $6$ です。

入力例 2

6 3
abcdef
abc

出力例 2

-1

入力例 3

15 9
dnsusrayukuaiia
dujrunuma

出力例 3

45