Contest: Task: Related: TaskB

Score : $300$ points

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.

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

Input is given from Standard Input in the following format:

$N$ $M$ $S$ $T$

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