Problem:
 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

Solution (Python):
import sys
n1,n2 = list( map(int, input().split()) )
s1 = input()
s2 = input()

def gcd(a,b):
    if b==0: return a
    return gcd(b, a%b)

t = gcd(n1,n2)

re = n1*n2//t

x1 = re//n1
x2 = re//n2

step = x1*x2 // gcd(x1,x2)

ii = 0
while ii <re:
    j1 = ii // x1 
    j2 = ii // x2
    if s1[j1]!= s2[j2]:
        print(-1)
        sys.exit()
    ii+=step
print(re)

Solution (Python):
n, m = map(int, input().split())
s = input()
t = input()

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

c = gcd(n, m)
flag = True
for i in range(c):
    if s[n * i // c] != t[m * i // c]:
        flag = False
        break
if flag == True:
    print(n * m // c)
else:
    print(-1)

Solution (Python):
def GCD(a, b):
    a, b = max(a, b), min(a, b)
    while a%b>0:
        a, b = b, a%b
    return b

N, M = map(int, input().split())
S = input()
T = input()
GCD = GCD(N, M)
LCM = N * M // GCD
sm, tm = N//GCD, M//GCD
for i in range(GCD):
    if S[i*sm] != T[i*tm]:
        print(-1)
        break
else:
    print(LCM)

Solution (Python):


def main():
    n, m = map(int, input().split())
    s = input()
    t = input()
    k = gcd(n, m)
    if s[::n // k] == t[::m // k]:
        print(n * m // k)
    else:
        print(-1)

def gcd(x, y):
    if x < y:
        x, y = y, x  
    while y > 0:
        r = x % y
        x = y
        y = r
    return x

main()

Solution (Python):
from fractions import gcd
N, M = map(int, input().split())
S = input()
T = input()
GCD = gcd(N, M)
s = S[::N//GCD]
t = T[::M//GCD]
if s != t:
  print(-1)
else:
  print(N * M // gcd(N, M))

Solution (Python):
N, M = map(int, input().split())
S = input()
T = input()

from fractions import gcd

g = gcd(N, M)
ans = N*M//g
n = ans//N
m = ans//M

for i in range(g):
    if S[i*m] != T[i*n]:
        print(-1)
        exit()
print(ans)

Solution (Python):
n,m=map(int,input().split())
s=input()
t=input()
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
def lcm(a, b):
    return a * b // gcd (a, b)
if gcd(n,m)==1:
    if s[0]==t[0]:
        print(lcm(n,m))
    else:
        print(-1)
else:
    a,b=n//gcd(n,m),m//gcd(n,m)
    x=[]
    y=[]
    for i in range(0,n,a):
        x.append(s[i])
    for i in range(0,m,b):
        y.append(t[i])
    if x==y:
        print(lcm(n,m))
    else:
        print(-1)

Solution (Python):
from fractions import gcd
def main():
    n, m = map(int, raw_input().split())
    s = raw_input().strip()
    t = raw_input().strip()
    g = gcd(n, m)
    l = n * m / g
    a = l / n
    b = l / m
    d = {}
    for i, x in enumerate(s):
        d[i*a] = x
    for i, x in enumerate(t):
        if i * b in d and d[i*b] != x:
            print -1
            return
    print l
main()

Solution (Python):
N, M = map(int, input().split())
S = input()
T = input()

"""
6 4
GCD=2
LCM=12
a.b.c.d.e.f.
a..b..c..d..
"""
def GCD(a, b):
    if a < b:
        a, b = b, a
    while b > 0:
        a, b = b, a%b
    return a

def LCM(a, b):
    return a * b // GCD(a, b)
  
X = LCM(N, M)
w = 0
while w < N*M:
  if S[w//M] == T[w//N]:
    w += X
    continue
  else:
    print(-1)
    exit(0)

print(X)

Solution (Python):
import fractions as frc
N,M=map(int,input().split())
S = input()
T = input()
L = (N*M)//frc.gcd(N,M)
n = L//N
m = L//M
d = {}
for i in range(N):
    d[n*i] = S[i]
for i in range(M):
    if m*i in d:
        if d[m*i] != T[i]:
            print(-1)
            exit()
print(L)

Solution (Python):
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a

N,M = map(int,input().split())
S = input()
T = input()
k = gcd(N,M)
n = N//k
m = M//k
flg = False
for i in range(k):
    if S[n*i] != T[m*i]:
        flg = True
if flg:
    print(-1)
else:
    print(N*m)

Solution (Python):
from fractions import gcd

n,m = map(int,input().split())
s = input()
t = input()
if n==m:
    if s!=t:
        print('-1')
        exit()
    else:
        print(n)
        exit()
elif n<m:
    n,m = m,n
    s,t = t,s

if n%m==0:
    k = n//m
    if s[::k]==t:
        print(n)
        exit()
    else:
        print('-1')
        exit()
else:
    g = gcd(n,m)
    if s[::n//g]==t[::m//g]:
        print(n*m//gcd(n,m))
    else:
        print(-1)

Solution (Python):
def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

N, M = map(int, input().split())
S = input()
T = input()

g = gcd(N,M)
l = N * M // g

n = N // g
m = M // g

for i in range(g):
    if S[n*i] != T[m*i]:
        print(-1)
        break
else:
    print(l)

Solution (Python):

N, M = map(int, input().split())
S = list(input())
T = list(input())

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

A = gcd(N, M)

res = M * N // A

for i in range(A):
    if S[i*(N // A)] != T[i*(M // A)]:
        res = -1
print(res)

Solution (Python):
def gcd(x,y):
    a=max(x,y)
    b=min(x,y)
    if a%b==0:
        return b
    else:
        return gcd(a%b,b)
def lcm(x,y):
    return (x*y)//gcd(x,y)
N,M=map(int,input().split())
S=input()
T=input()
X=lcm(N,M)
Y=gcd(N,M)
A=N//Y
B=M//Y
for i in range(Y):
    if S[i*A]!=T[i*B]:
        print(-1)
        exit()
print(X)

Solution (Python):
import fractions
N,M = map(int,input().split())
S = input()
T = input()
g = fractions.gcd(N,M)
lcm = N*M // g

for i in range(g):
    a = S[N//g * i]
    b = T[M//g * i]
    if a != b:
        print(-1)
        exit()
print(lcm)

Solution (Python):
N,M=map(int,raw_input().split())

S= raw_input()
T= raw_input()

def gcd(a,b):
    g=1
    for i in range(1,min(a,b)+1):
        if a%i==0 and b%i==0:
            g=i
    return g
    
g=gcd(N,M)

flag=True
for i in range(g):
    if S[i*(N/g)]!=T[i*(M/g)]:
        flag=False
        break

if flag:
    print N*M/g
else:
    print -1

Solution (Python):
n,m = (int(i) for i in input().split())
s = input()
t = input()
def gcd(a,b):
	if a%b: return gcd(b,a%b)
	else: return b
g = gcd(n,m)
ng,mg = n//g,m//g
if all(s[i*ng]==t[i*mg] for i in range(g)): print(n*m//g)
else: print(-1)

Solution (Python):
import math
def gcd(a, b):
    
    
    if a < b:
        return gcd(b, a)
    if b == 0:
        return a
    else:
        c = a % b
        return gcd(b, c)

def lcm(a, b):
    return (a * b // gcd(a, b))

n, m = map(int, input().split())

s = input()
t = input()

d = gcd(n, m)
l = lcm(n, m)

for i in range(d):
    if s[i * (n // d)] != t[i * (m // d)]:
        print(-1)
        exit()
print(l)

Solution (Python):

import sys
try: from typing import Any, Union, List, Tuple, Dict
except ImportError: pass
sys.setrecursionlimit(10**6)
def debug(*args): print(*args, file=sys.stderr)
def exit(): sys.exit(0)


N, M = map(int, input().split())
S = input()
T = input()


def gcd(a, b):
    
    "最大公約数を計算する．0とか負の数が入るとヤバい"
    if b%a == 0:
        return a
    return gcd(b%a, a)


d = gcd(N, M)
n = N // d
m = M // d


for i in range(d):
    if S[i*n] != T[i*m]:
        print(-1)
        exit()
print(n*m*d)

Solution (Python):
from sys import exit, setrecursionlimit, stderr
from functools import reduce
from itertools import *
from collections import defaultdict, Counter
from bisect import bisect
from fractions import gcd

def read():
  return int(input())

def reads():
  return [int(x) for x in input().split()]

N, M = reads()
S = input()
T = input()
g = gcd(N, M)
a = N // g
b = M // g
possible = all(S[a*i] == T[b*i] for i in range(g))
print(N * b if possible else -1)

Solution (Python):
import fractions

N,M = map(int, raw_input().split())
S = raw_input()
T = raw_input()

g = fractions.gcd(N, M)
ans = N*M/g
for i in range(g):
  if S[i*N/g] != T[i*M/g]:
    ans = -1
print ans

Solution (Python):

import sys

input=sys.stdin.readline

n,m=map(int,input().split())
s=input().strip()
t=input().strip()

prod=n
while prod%m!=0: prod+=n

d={}
for i in range(n):
    d[(prod//n)*i]=s[i]
for i in range(m):
    j=(prod//m)*i
    if (j in d) and (d[j]!=t[i]):
        print("-1")
        break
else:
    print(prod)

Solution (Python):
from fractions import gcd


def solve(n, m, s, t):
    g = gcd(n, m)
    ng = n // g
    mg = m // g

    for h in range(g):
        if s[ng * h] != t[mg * h]:
            return -1
    return ng * mg * g


n, m = list(map(int, input().split()))
s = input()
t = input()
print(solve(n, m, s, t))