得分 : $300$ 分

问题描述

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

一个字符串 $X$ 被称为 好字符串 当满足以下所有条件：

• 设 $L$ 为 $X$ 的长度。$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