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):
n, m = [int(x) for x in input().split()]
s, t = [input() for _ in range(2)]

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

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

l = lcm(n, m)
nn, mm = l//m, l//n

for k in range(l//(nn*mm)):
    if s[k*nn] != t[k*mm]:
        print(-1)
        break
else:
    print(l)

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

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

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

L = lcm(N,M)
G = gcd(N,M)
n = L//N
m = L//M

s = [S[i*m] for i in range(G)]
t = [T[i*n] for i in range(G)]

if s == t or (G == 1 and S[0]==T[0]):
    print(L)
else:
    print(-1)

Solution (Python):


import sys


input = sys.stdin.readline
INF = float('inf')


def inpl(): return list(map(int, input().split()))



def gcd(x, y):
    if x % y == 0:
        return y
    else:
        x, y = y, x % y
        return gcd(x, y)


def lcm(x, y):
    return x * y // gcd(x, y)


N, M = inpl()
S = input()
T = input()

L = lcm(N, M)
LCM = lcm(L//N, L//M)


ss = L // N
cnt = 0
tmp = 0
S_li = [S[0]]
while tmp <= L:
    tmp = ss * cnt + 1
    if tmp % LCM == 1:
        S_li.append(S[cnt])
    cnt += 1

tt = L // M
cnt = 0
tmp = 0
T_li = [T[0]]
while tmp < L:
    tmp = tt * cnt + 1
    if tmp % LCM == 1:
        T_li.append(T[cnt])
    cnt += 1



if S_li == T_li:
    print(L)
else:
    print(-1)

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

def _gcd(a,b):
  while b>0:
    a,b=b,a%b
  return a

gcd = _gcd(N,M)
lcm = N*M//gcd

def check():
  a,b = 0,0
  da,db = N//gcd, M//gcd
  while a < N:
    if S[a]!=T[b]:
      print(-1)
      return
    a+=da
    b+=db
  print(lcm)

check()

Solution (Python):
import fractions


def main():
    n, m = map(int, input().split())
    s = input()
    t = input()
    l = n * m // fractions.gcd(n, m)
    x = {}
    for i in range(n):
        x[i * (l // n)] = s[i]
    for i in range(m):
        if i * (l // m) not in x:
            continue
        if x[i * (l // m)] != t[i]:
            print(-1)
            return
    print(l)


if __name__ == '__main__':
    main()

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

def lcm(x, y):
    return (x * y) // gcd(x, y)



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

MA = [S[0]]
NA = [T[0]]

L = lcm(M, N)

m = L/M
n = L/N

for i in range(M):
    if i % n == 0:
        MA.append(S[i])

for i in range(N):
    if i % m == 0:
        NA.append(T[i])

if MA == NA:
    print(L)
else:
    print("-1")

Solution (Python):
import fractions
n, m = map(int, input().split())
s = list(input())
t = list(input())
u = fractions.gcd(n, m)
l = n * m // u
n = n//u
m = m // u
for i in range(u):
    if s[i * n] != t[i * m]:
        l = -1
        break
print(l)

Solution (Python):
l = raw_input().split()

N = int(l[0])
M = int(l[1])

strA = raw_input()
strB = raw_input()



nmgcd = N
eu = M

while eu:
	nmgcd, eu = eu, nmgcd % eu


nmlcm = (N*M)//nmgcd




itr = 0

for i in range(nmgcd):
    if strA[0+i*(nmlcm//M)] == strB[0+i*(nmlcm//N)]:
        itr = itr +1

if itr == nmgcd:
    print(nmlcm)
else:
    print(-1)

Solution (Python):
import fractions

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

l = n * m // fractions.gcd(n, m)
ans = l
dic = {}
for i in range(n):
    j = (l // n) * i % l
    if j in dic and dic[j] != s[i]:
        ans = -1
        break
    dic[j] = s[i]
for i in range(m):
    j = (l // m) * i % l
    if j in dic and dic[j] != t[i]:
        ans = -1
        break
    dic[j] = t[i]
print(ans)

Solution (Python):
import fractions


def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)


n, m = [int(_) for _ in input().split()]
s = input()
t = input()
a = lcm(n, m)
s_a = a // n
t_a = a // m
p = lcm(s_a, t_a)
result = True
for i in range(a//p):
    if s[(i*p)//s_a] != t[(i*p)//t_a]:
        result = False
if result:
    print(a)
else:
    print(-1)

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

nm = input().split()
n = int(nm[0])
m = int(nm[1])
s = input()
t = input()
g = gcd(m,n)

ans = int(n*m / g)
for i in range(g):
    if s[(n//g)*i] != t[(m//g)*i]:
        ans = -1
            
print(ans)

Solution (Python):
import numpy as np
import scipy
def gcd(a, b):
    if a % b:
        return gcd(b, (a % b))
    else:
        return b
N, M = map(int,input().split())
S = input()
T = input()
t = gcd(N,M)
n = N // t
m = M // t
ans = n * m * t
for i in range(t):
    if(S[n*i]!=T[m*i]):
        ans = -1
        break
print(ans)

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

L = int(N * M / fractions.gcd(N, M))
LN = int(L / N)
LM = int(L / M)

count = 0
dic1 = {LN*n:S[n] for n in range(N)}
dic2 = {LM*n:T[n] for n in range(M)}

for k in dic1.keys():
    if k in dic2 and dic1[k] != dic2[k]:
        count += 1
        print(-1)
        break

if count == 0:
    print(L)

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()

c = gcd(N,M)

d = M * (N // c)

a1 = d // N
a2 = d // M


for i in range(min(N//a2,M//a1)):
    if S[a2*i] != T[a1*i]:
        print(-1)
        exit()

print(d)

Solution (Python):
def lcm(a, b):
    small = min(a, b)
    large = max(a, b)
    gcd = small
    while large % small != 0:
        tmp = small
        small = large % small
        large = tmp
        gcd = small

    return(a * b // gcd)


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

lcm_nm = lcm(N, M)
s_base = lcm_nm // M
t_base = lcm_nm // N
i = 0
while s_base * i < N and t_base * i < M:
    if S[i * s_base] != T[i * t_base]:
        print(-1)
        exit()
    i += 1

print(lcm_nm)

Solution (Python):
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
def lcm(a, b):
    return a * b // gcd (a, b)
n, m = map(int, input().split())
S = input()
T = input()
jn = 0
jm = 0
l = lcm(n,m)
ln = l // n
lm = l // m
d = lcm(ln, lm)
for i in range(0, l, d):
    if S[i // ln] != T[i // lm]:
        print(-1)
        exit()
print(l)

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


def lcm(x, y):
    return (x * y) // gcd(x, y)


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

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

ng = n // g
mg = m // g
k = 0
flg = True
while True:
    if k * ng >= n or k * mg >= m:
        break
    if s[k * ng] != t[k * mg]:
        flg = False
        break
    k += 1

if flg:
    print(l)
else:
    print(-1)

Solution (Python):


def lcm(a, b): 
    def gcd(a, b):  
        if b == 0:
            return a
        else:
            return gcd(b, a % b)
    
    return a * b // gcd(a, b)

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

l = lcm(N, M)

ans = {}
flag = True

for i in range(N):
    now = (l // N) * i + 1
    ans[now] = S[i]

for i in range(M):
    now = (l // M) * i + 1
    if now in ans:
        if ans[now] != T[i]:
            flag = False
            break

if flag:
    print(l)
else:
    print(-1)

Solution (Python):
import fractions


def lcm(x, y):
    return x // fractions.gcd(x, y) * y


def solve(n, m, s, t):
    le = lcm(n, m)
    s_new_ps = {le // n * i for i in range(n)}
    t_new_ps = {le // m * i for i in range(m)}
    conf_new_ps = s_new_ps & t_new_ps
    for p in conf_new_ps:
        i = p // (le // n)
        j = p // (le // m)
        if s[i] != t[j]:
            return None
    return le


def main():
    n, m = (int(z) for z in input().split())
    s = input()
    t = input()
    res = solve(n, m, s, t)
    if res is None:
        print(-1)
    else:
        print(res)


if __name__ == '__main__':
    main()

Solution (Python):
from fractions import gcd
from functools import reduce

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

def lcm(numbers):
    return reduce(lcm_base, numbers, 1)


N, M = map(int,input().split(' '))
S = input()
T = input()
L = lcm([N,M])
L_N = L // N
L_M = L // M
nowN = 0
nowM = 0
countN = 0
countM = 0
while True:


    if nowN < nowM:
        nowN += L_N
        countN +=1
    elif nowM < nowN:
        nowM += L_M
        countM +=1
    elif nowM == nowN:


        if S[countN] != T[countM]:
            print('-1') 
            exit()
        else:
            countN +=1
            nowN += L_N
    if nowN >= L and nowM >= L:
        print(str(L))
        exit()

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

def gcd(m,n):
    x = max(m,n)
    y = min(m,n)
    if x%y == 0:
        return y
    else:
        while x%y != 0:
            z = x%y
            x = y
            y = z
        else:
            return z

def lcm(m,n):
    return int(m * n /gcd(m,n))

d = gcd(N,M)
l = lcm(N,M)

s = [0 for i in range(0,d)]
t = [0 for i in range(0,d)]

a = int(l/M)
b = int(l/N)

for i in range(0,d):
    s[i] = S[i*a]
    t[i] = T[i*b]

if s == t:
    print(l)
else:
    print(-1)

Solution (Python):
from fractions import gcd
def lcm(x,y):
  return (x*y)//gcd(x,y)
  
n,m=map(int,input().split())
s=input()
t=input()
c=0
a=lcm(n,m)//n
b=lcm(n,m)//m


for i in range(n):
  if int(i*a)%b==0:
    if s[i]==t[int(i*a/b)]:c+=1
    else:
      break
if c==(int(lcm(n,m)/lcm(a,b))):print(lcm(n,m))
else:print(-1)

Solution (Python):
from fractions import gcd

def lcm(x, y):
    return (x * y) // gcd(x, y)

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

LCM = lcm(N,M)
GCD = gcd(N,M)

for i in range(0,LCM,LCM//GCD):
    if S[i*N//LCM] != T[i*M//LCM]:
        print(-1)
        exit()
print(LCM)

Solution (Python):
def gcd(x, y):
    if x == 0:
        return y
    elif y == 0:
        return x
    elif x % 2 == 0 and y % 2 == 0:
        return 2 * gcd(x//2, y//2)
    elif x % 2 == 0:
        return gcd(x//2, y)
    elif y % 2 == 0:
        return gcd(x, y//2)
    elif y >= x:
        return gcd(x, (y-x)//2)
    else:
        return gcd((x-y)//2, y)


n, m = tuple(map(int, input().split()))
s = list(input())
t = list(input())
g = gcd(n, m)
ng = n // g
mg = m // g
res = n * m // g
for i in range(0, g):
    if s[ng * i] != t[mg * i]:
        res = -1
        break

print(res)

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()
gcd = gcd(N, M)

sl = [i for i in range(0, N, N//gcd)]
tl = [i for i in range(0, M, M//gcd)]
for i in range(len(sl)):
    if S[sl[i]] != T[tl[i]]:
        print(-1)
        break
else:
    print(N*M//gcd)

Solution (Python):


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

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

l = lcm(N,M)

if S[::l//M] == T[::l//N]:
    print(l)
else:
    print(-1)

Solution (Python):
import fractions

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


N, M = [int(i) for i in input().split()]
s = input()
t = input()

L = lcm(N, M)
l_to_s = {}
for i in range(N):
    l_to_s[1 + i * (L // N)] = i
l_to_t = {}
for i in range(M):
    l_to_t[1 + i * (L // M)] = i

ans = L
for k, v in l_to_s.items():
    if k in l_to_t:
        if s[v] != t[l_to_t[k]]:
            ans = -1
            break

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
 
if gcd(N,M) == 1:
	if S[0]==T[0]:
		print(N*M)
	else:
		print(-1)
else:
	tmp = gcd(N,M)
 
	ans = True
	for i in range(tmp):
		if S[N//tmp*i] != T[M//tmp*i]:
			ans = False
	if ans == True:
		print(N * M // tmp)
	else:
		print(-1)

Solution (Python):

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

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

tmpans = N * M // gcd(N, M)
S_intv = tmpans // N
T_intv = tmpans // M

for sidx, si in enumerate(S):
    
    idx = sidx * S_intv
    if idx % T_intv > 0: continue
    
    tidx = idx // T_intv
    if si != T[tidx]:
        ans = -1
        break
else:
    ans = tmpans

print(ans)

Solution (Python):
from fractions import gcd
def lcm(x, y):
  return (x * y) // gcd(x, y)
n,m=map(int,input().split())
x=lcm(n,m)
y=x//gcd(n,m)
a=input()
b=input()

for i in range(x//y):
  if a[(x//m)*i] != b[(x//n)*i]:
    print(-1)
    exit()
print(x)

Solution (Python):





"""
AGC028 A
"""

import fractions

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

g = fractions.gcd(n, m)
lcm = (n*m//g)

flag = True
for i in range(g):
    if s[i*lcm//m] != t[i*lcm//n]:
        flag = False
        break

if flag:
    print(lcm)
else:
    print(-1)

Solution (Python):
import math

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

N, M = list(map(int, input().split()))
S = input()
T = input()
g = gcd(N, M)
lcm = N*M//g
if N%M==0 or M%N==0:
    exist = True
    if N>M:
        for i in range(M):
            if S[N//M*i]!=T[i]:
                exist = False
                break
    else:
        for i in range(N):
            if T[M//N*i]!=S[i]:
                exist = False
                break
    if exist:
        print(max(N, M))
    else:
        print(-1)
else:
    n_s = lcm//N
    n_t = lcm//M
    mul = n_s*n_t
    exist = True
    for i in range(0, lcm, mul):
        if S[i//n_s]!=T[i//n_t]:
            exist = False
            break
    if exist:
        print(lcm)
    else:
        print(-1)

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

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

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

L = lcm(N, M)
n = L//N
m = L//M

sub_S = S[::m]
sub_T = T[::n]

if sub_S == sub_T:
    print(L)
else:
    print(-1)

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

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

n,m = [int(x) for x in input().split()]
s = input()
t = input()
l = lcm(n,m)
d = {}
for i in range(n):
  d[i * l / n] = s[i]
for i in range(m):
  if i in d and d[i * l / m] != t[i]:
    l = -1
    break

print(int(l))

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

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

def f(a, b):
    if b < a:
        a, b = b, a
    
    while b % a != 0:
        a, b = b % a, a
    return a

if S[0] != T[0]:
    print(-1)

else:
    p = f(N, M)
    k = N // p
    l = M // p

    for n in range(p):
        if S[n * k] != T[n * l]:
            print(-1)
            break
    else:
        print(N * M // p)

Solution (Python):
N, M = map(int, input().split())
def euc(n,m):
    if n%m == 0:
        return m
    else:
        return euc(m, n%m)
g = euc(N, M)
l = int(N*M/g)
S = input()
T = input()
steps = int(l/M)
stept = int(l/N)
stepnumber = int(N / steps)

for i in range(stepnumber):
    if S[i*steps] != T[i*stept]:
        print(-1)
        break
else:
    print(l)

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

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

sdic = {}
for k in range(0, len(s)):
    sdic[k*m] = s[k]
tdic = {}
for k in range(0, len(t)):
    tdic[k*n] = t[k]
ok = 1
for skey in sdic.keys():
    try:
        if tdic[skey] != sdic[skey]:
            ok = -1
    except:
        pass
    
if ok == 1:
    print(int(m * n / gcd(m,n)))
else:
    print('-1')

Solution (Python):

def gcd(a,b):
    a, b = max(a,b), min(a,b)
    d = 1
    while a > b > 0:
        if a&1 == b&1 == 0:
            a >>= 1
            b >>= 1
            d <<= 1
        else:
            a, b = b, a%b
    d *= a
    return d

def solve():
    N, M = map(int,input().split())
    S = input()
    T = input()
    D = gcd(N,M)
    a = N//D
    b = M//D
    for i, j in zip(range(0,N,a), range(0,M,b)):
    	if S[i] != T[j]:
    		return '-1'
    L = N*M//D
    return str(L)

if __name__ == '__main__':
    print(solve())

Solution (Python):


from fractions import gcd

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

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

for i, j in zip(S[::N//g], T[::M//g]):
    if i != j:
        print(-1)
        break
else:
    print(l)

Solution (Python):

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


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

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

jkl = (n-1)//(n//g)+1
nn = n//g
mm = m//g

c = 0
for i in range(jkl):

    if s[i*nn]==t[i*mm]:
        c += 1
    
if c == jkl:
    print(l)
else:
    print(-1)

Solution (Python):
n,m = (int(i) for i in input().split())
s = str(input())
t = str(input())
gcd = 0
r = n%m
n_gcd = n
m_gcd = m
while(r != 0):
    n_gcd = m_gcd
    m_gcd = r
    r = n_gcd%m_gcd
gcd = m_gcd
L_min = int(n*m/gcd)
flg = 1
for i in range(gcd):
    if s[int(n/gcd)*i]!= t[int(m/gcd)*i]:
        flg = 0
        break
if flg==1:
    print(L_min)
else:
    print(-1)

Solution (Python):
import fractions

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

s = list(input())
t = list(input())

l = len(s)
u = len(t)

a = fractions.gcd(l,u)
b = (l*u)//a

for i in range(a):
	if s[(l//a)*i]  != t[(u//a)*i]:
		print(-1)
		break
else:
	print(b)

Solution (Python):
from fractions import gcd
N, M = map(int, input().split())
S = input()
T = input()
lcm = N * M // gcd(N, M)
tmp = {}
for s, i in zip(S, range(0, lcm, lcm//N)):
    tmp[i] = s
is_ans = True
for t, i in zip(T, range(0, lcm, lcm//M)):
    if i in tmp:
        if tmp[i] == t:
            continue
        is_ans = False
        break
if is_ans:
    print(lcm)
else:
    print(-1)

Solution (Python):
from fractions import gcd

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

s = input()
t = input()


l = (n * m) // gcd(n, m)

p = l // n
q = l // m
r = (p * q) // gcd(p, q)

ans = l

for i in range(l//r):
    if s[r//p*i] != t[r//q*i]:
        ans = -1
        break

print(ans)

Solution (Python):
import fractions

[n, m] = list(map(int, input().split()))
s = input()
t = input()

flag = False
gcd = fractions.gcd(n, m)
lcm = n * m // gcd
if s[0] == t[0]:
    if gcd == 1:
        flag = True
    else:
        if s[::lcm//len(t)] == t[::lcm//len(s)]:
            flag = True
if flag:
    print(lcm)
else:
    print(-1)

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

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


l = n * m // gcd(n, m)

ok = True
nn = l // n
mm = l // m

i = 0
j = 0

while True:
    if i < j:
        i += nn
    elif j < i:
        j += mm
    else:
        if i // nn < n and j // mm < m:
            if s[i // nn] != t[j // mm]:
                ok = False
        else:
            break
        i += nn
    

print(l if ok else -1)

Solution (Python):
n, m=map(int, raw_input().split())
s=raw_input()
t=raw_input()
def gcd(a, b):
	if b==0:
		return a
	else:
		return gcd(b, a%b)
g=gcd(n, m)
l=n*m/g
for i in range(g):
	if s[n/g*i]!=t[m/g*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())
Ss = input()
Ts = input()

g = gcd(N, M)
ds, dt = N // g, M // g

if Ss[::ds] == Ts[::dt]:
    print(N * M // g)
else:
    print(-1)

Solution (Python):
from fractions import gcd

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

Solution (Python):
import sys
import socket

if socket.gethostname() in ['N551J', 'F551C']:
    sys.stdin = open('a1.in')


def read_int_list():
    return list(map(int, input().split()))


def read_int():
    return int(input())


def read_str_list():
    return input().split()


def read_str():
    return input()


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


def solve():
    n, m = read_int_list()
    a = read_str()
    b = read_str()
    d = gcd(n, m)
    if a[::n // d] == b[::m // d]:
        lcm = n * m // d
        return lcm
    return -1


def main():
    res = solve()
    print(res)


if __name__ == '__main__':
    main()

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

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

def lcm(a, b):
    g = gcd(a, b)
    g_a = a // g
    g_b = b // g
    return g_a * g_b * g

L = lcm(n, m)
s1 = L // n
t1 = L // m
l = lcm(s1, t1)

flag = 0
for i in range(L//l):
    if s[i*t1] != t[i*s1]:
        flag = 1

if flag:
    print(-1)
else:
    print(L)

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

if gcd(N,M) == 1:
	if S[0]==T[0]:
		print(N*M)
	else:
		print(-1)
else:
	tmp = gcd(N,M)

	ans = True
	for i in range(tmp):
		if S[N//tmp*i] != T[M//tmp*i]:
			ans = False
	if ans == True:
		print(N * M // tmp)
	else:
		print(-1)

Solution (Python):



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

def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)

k = gcd(n,m)
k_n = int(n/k) 
k_m = int(m/k) 

s_a = s[0::k_n]
t_a = t[0::k_m]

if s_a == t_a:
    print(int(n*m/k))
else:
    print(-1)

Solution (Python):
import fractions

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

gcd_N_M = fractions.gcd(N, M)
lcm_N_M = N*M//gcd_N_M
if S[0::N//gcd_N_M] == T[0::M//gcd_N_M]:
    print(lcm_N_M)
else:
    print(-1)

Solution (Python):

from sys import stdin

s_in = lambda: stdin.readline()[:-1] 
d_in = lambda: int(stdin.readline()) 
ds_in = lambda: list(map(int, stdin.readline().split())) 

N, M = ds_in()
S = s_in()
T = s_in()


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



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

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

print(lcm_NM)

Solution (Python):
def getN():
    return int(input())


def getNM():
    return map(int, input().split())


def getList():
    return list(map(int, input().split()))

def gcd(n,m):
    if n > m:
        n,m = m,n
    while (m % n != 0):
        temp = n;
        n = m % n;
        m = temp;
    return n;

def lcm(m,n):
    return int(m*n/gcd(m,n))

N,M = getNM()

s = input()
t = input()

lcm = lcm(N,M)
ks, kt = lcm//N, lcm//M
order = {}
flag = 1
i = 0
for alp in s:
    order[ks*i+1] = alp
    i += 1

j= 0
for alp in t:
    num = kt*j+1
    try:
        if order[num] != alp:
            flag = 0
    except:
        pass
    j += 1

if flag:
    print(lcm)
else:
    print("-1")

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

f=lambda x,y:x*y//gcd(x,y)
n,m=map(int,input().split())
s,t=input(),input()
lcm=f(n,m)
a,b=lcm//n,lcm//m
d={}

for i in range(n):
  d[i*a]=s[i]
for i in range(m):
  if i*b in d and d[i*b]!=t[i]:
    print(-1)
    break
  d[i*b]=t[i]
else:
  print(lcm)

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

N, M = map( int, input().split())
g = gcd(N,M)
S = input()
T = input()
c = M//g
t = N//g
ans = M*N//g
for i in range(N):
    if c*i%t == 0:
        if S[i] != T[c*i//t]:
            ans = -1
print(ans)

Solution (Python):
import math
import fractions

n, m = [int(i) for i in input().split()]
s = input()
t = input()

ans = n * m // fractions.gcd(n, m)

for scnt in range(n):
    if scnt * m % n == 0:
        tcnt = scnt * m // n
        if s[scnt] != t[tcnt]:
            ans = -1
            break

print(ans)

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


def main():
    n, m = map(int, raw_input().split())
    s = raw_input().strip()
    t = raw_input().strip()
    g = gcd(n, m)
    lcm = n * m / g
    a = lcm / m
    b = lcm / n
    if s[::a] == t[::b]:
        print lcm
    else:
        print -1


if __name__ == '__main__':
    main()

Solution (Python):




def gcd(a, b):
    if not b:
        return a
    return gcd(b, a % b)


def main():
    n, m = map(int, input().split())
    s, t = input(), input()
    l = n // gcd(n, m) * m

    dic = {}
    for i in range(n):
        dic[i*l//n+1] = s[i]

    for i in range(m):
        if i * l // m + 1 in dic and dic[i*l//m+1] != t[i]:
            print(-1)
            exit()

    print(l)


if __name__ == '__main__':
    main()

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

from fractions import gcd
L = N*M//gcd(N,M)

ds = L//N

dt = L//M


print(L if S[::dt]==T[::ds] else -1)

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


n,m = map(int, input().split())
s = str(input())
t = str(input())
lcm = (n*m) // gcd(n,m)

ind_s = lcm // m
ind_t = lcm // n

list_s = s[0::ind_s]
list_t = t[0::ind_t]

if list_s == list_t:
	print(lcm)
else:
	print(-1)

Solution (Python):

import fractions


def gcd(x, y):
    return int(fractions.gcd(x, y))


def lcm(x, y):
    return x * y // gcd(x, y)


tmp = input()
N, M = [int(a) for a in tmp.split()]
S = str(input())
T = str(input())
S_len = len(S)
T_len = len(T)

check_num = gcd(S_len, T_len)
S_skip = S_len // check_num
T_skip = T_len // check_num

ok = True
S_i = T_i = 0
for i in range(check_num):
    if S[S_i] != T[T_i]:
        ok = False
        break
    S_i += S_skip
    T_i += T_skip

if ok:
    print(lcm(S_len, T_len))
else:
    print(-1)

Solution (Python):
import math
import fractions
n,m = map(int,input().split())
lis = []
nn = n
mm = m
for i in range(2,math.ceil(math.sqrt(max(n,m)))+1):
  while nn % i == 0 and mm % i == 0:
    nn = nn // i
    mm = mm // i
num = (n * m)// fractions.gcd(n,m)
s = str(input())
t = str(input())
s = s[::nn]
t = t[::mm]
if s == t:
  print(num)
else:
  print("-1")

Solution (Python):
def gcd(a, b):
    if b == 0:
        return a
    return gcd(b, a%b)
    
def lcm(a, b):
	return a * b // gcd (a, b)
	
	
a = input().split()
a = [int(i) for i in a]

string1 = input()
string2 = input()

num = lcm(len(string1), len(string2))

counter = 0

one = num//len(string1)
two = num//len(string2)

ok = True
while counter*two < len(string1) and counter*one < len(string2):
	if string1[two*counter] == string2[one*counter]:
		pass
	else:
		ok = False
		break
	counter +=1
	
if ok == True:
	print(num)
else:
	print(-1)

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

k = N * M // gcd(N, M)
if  all(s == t for s, t in zip(S[::k // M], T[::k // N])):
    print(k)
else:
    print(-1)

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

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

g = gcd(N, M)
if S[0::N//g] == T[0::M//g]:
  print(N*M//g)
else:
  print(-1)

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

for k in range(min(n,m), 0, -1):
    if n%k==0 and m%k==0:
        l = k
        break

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

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



for i in range(1,M+1):
    if N*i%M==0:
        break

ANS=N*i

check=1
for i in range(N):
    s=S[i]
    if (i*M)%N==0:
        t=T[(i*M)//N]
        if s!=t:
            check=0
            
            break

if check==1:
    print(ANS)
else:
    print(-1)

Solution (Python):


import fractions

n,m=[int(i) for i in input().split()]
s=input()
t=input()

g = fractions.gcd(n,m)
l = n * m // g

ok=1
for i in range(g):


    if s[i*n//g] != t[i*m//g]:
        ok=0


if ok:
    print(l)
else:
    print(-1)

Solution (Python):
import sys
stdin = sys.stdin

sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

def get_gcd(a:int, b:int) -> int:
    while b:
        a, b = b, a % b
    return a
    
def get_lcm(a:int, b:int) -> int:
    return (a // get_gcd(a,b)) * b

n,m = li()
s = lc()
t = lc()

sx = dict()
tx = dict()

lcm = get_lcm(n,m)

for idx, i in enumerate(range(1,lcm+1,lcm//n)):
    sx.update({i:s[idx]})

for idx, j in enumerate(range(1,lcm+1,lcm//m)):
    tx.update({j:t[idx]})
    
common_key = list(set(list(sx.keys())) & set(list(tx.keys())))

exist = True
for c in common_key:
    if sx[c] != tx[c]:
        exist = False
        break
    
if exist:
    print(lcm)
else:
    print(-1)

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

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

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

ans = -1
i = 0
while i*n < N:
    if S[i*n] != T[i*m]:
        break
    i+=1
else:
    ans = N*M//G

print(ans)

Solution (Python):
from fractions import gcd

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

gcd_ = gcd(N, M)
lcm_ = N * M // gcd_
for i in range(gcd_):
    if S[i * N // gcd_] != T[i * M // gcd_]:
        print(-1)
        quit()
print(lcm_)

Solution (Python):
import math
import sys
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)
ans = lcm(n,m)
n1 = ans//n
m1 = ans//m
atai = {}
for i in range(n):
  atai[i*n1+1] = s[i]
for i in range(m):
  kaku = atai.get(i*m1+1, -1)
  if kaku != -1 and kaku != t[i]:
    print(-1)
    exit()
print(ans)

Solution (Python):
N, M = map(int, input().split())
S = list(input())
T = list(input())
def gcd(a, b):
    while b > 0:
        a, b = b, a%b
    return a

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

L = lcm(N, M)
d1 = L//N
d2 = L//M
if S[::d2] == T[::d1]:
    print(L)
else:
    print(-1)