Home

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$

Sample Input 1

3 2
acp
ae

Sample Output 1

6

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

Sample Input 2

6 3
abcdef
abc

Sample Output 2

-1

Sample Input 3

15 9
dnsusrayukuaiia
dujrunuma

Sample Output 3

45