﻿ AGC028 A - Two Abbreviations - Atcoder

# Home

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.

### 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