题目描述

長さ $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$ になる

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

输入格式

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

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

输出格式

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

题目大意

AT4435 [AGC028A]两个缩写

题目描述

给定一个长度为 N 的字符串 S 和一个长度为 M 的字符串 T ，这些字符串由小写英文字符组成。

当一个字符串 X 满足以下条件时，称为好字符串 （good string） 。

• X 的长度 L 可以被 N 和 M 整除
• 连接 X 的 1, L / N +1,2× L / N +1, ...( N −1)× L / N +1 且不改变顺序，结果为 S
• 连接 X 的 1, L / M +1,2× L / M +1, ...( M −1)× L / M +1 且不改变顺序，结果为 T

判断是否存在好字符串。如果存在，请找到最短的此类字符串的长度。

---

输入格式

按照以下格式标准输入：

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

---

输出格式

如果不存在任何一个好字符串，则输出 -1 ；如果存在，则打印最短的此类字符串的长度。

---

输入输出样例

样例见原题面

---

制约

• 1≤ N , M ≤10^5
• S , T 由小写字母组成
• ∣ S ∣= N
• ∣ T ∣= M

---

样例说明1

accept 字符串是一个好字符串。没有比这更短的字符串了，所以答案是6。

3 2
acp
ae

6

6 3
abcdef
abc

-1

15 9
dnsusrayukuaiia
dujrunuma

45

提示

制約

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

Sample Explanation 1

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