配点 : $300$ 点

問題文

長さ $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 と出力せよ。 存在するならば、その中で最短のものの長さを出力せよ。

3 2
acp
ae

6

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

6 3
abcdef
abc

-1

15 9
dnsusrayukuaiia
dujrunuma

45