题目描述

给定一个长度为 $N$ 的字符串 $S$ 和一个长度为 $M$ 的字符串 $T$。当且仅当一个字符串 $X$ 同时满足以下条件时，称其为好字符串：

• $X$ 的长度 $L$ 可以被 $N$ 和 $M$ 整除。
• 连接 $X$ 的第 $1,\frac{L}{N}+1,2\times \frac{L}{N}+1,\dots,(N−1)\times \frac{L}{N}+1$ 位且不改变顺序，结果为 $S$。
• 连接 $X$ 的第 $1,\frac{L}{M}+1,2\times \frac{L}{M}+1,\dots,(N−1)\times \frac{L}{M}+1$ 位且不改变顺序，结果为 $T$。

你需要判断是否存在好字符串。如果存在，请求出最短的好字符串的长度。

输入格式

第一行两个用空格分隔的正整数 $N,M$。

第二行一个仅包含小写字母的字符串 $S$。

第三行一个仅包含小写字母的字符串 $T$。

输出格式

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

样例 1

输入

3 2
acp
ae

输出

6

样例 2

输入

6 3
abcdef
abc

输出

-1

样例 3

输入

15 9
dnsusrayukuaiia
dujrunuma

输出

45

说明/提示

【样例解释】

字符串 accept 是一个好字符串。不难证明，不存在比这更短的好字符串，故答案为 $6$。

【数据范围】

对于 $100\%$ 的数据，$1\le N,M\le10^5$，$S,T$ 仅包含小写字母，且 $|S|=N$，$|T|=M$。