Score : $300$ points

Problem Statement

You are given a string $S$ of length $N$ and another string $T$ of length $M$. These strings consist of lowercase English letters.

A string $X$ is called a good string when the following conditions are all met:

• Let $L$ be the length of $X$. $L$ is divisible by both $N$ and $M$.
• Concatenating the $1$-st, $(\frac{L}{N}+1)$-th, $(2 \times \frac{L}{N}+1)$-th, $...$, $((N-1)\times\frac{L}{N}+1)$-th characters of $X$, without changing the order, results in $S$.
• Concatenating the $1$-st, $(\frac{L}{M}+1)$-th, $(2 \times \frac{L}{M}+1)$-th, $...$, $((M-1)\times\frac{L}{M}+1)$-th characters of $X$, without changing the order, results in $T$.

Determine if there exists a good string. If it exists, find the length of the shortest such string.

Constraints

• $1 \leq N,M \leq 10^5$
• $S$ and $T$ consist of lowercase English letters.
• $|S|=N$
• $|T|=M$

Input

Input is given from Standard Input in the following format:

$N$ $M$

$S$

$T$

Output

If a good string does not exist, print -1; if it exists, print the length of the shortest such string.

3 2
acp
ae

6

For example, the string accept is a good string. There is no good string shorter than this, so the answer is $6$.

6 3
abcdef
abc

-1

15 9
dnsusrayukuaiia
dujrunuma

45