题目描述

给定长度为$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