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):
from fractions import gcd
import sys

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

s_step = N // cd
t_step = M // cd
s_index = 0
t_index = 0

while s_index < len(S) and t_index < len(T):
    if S[s_index] != T[t_index]:
        print(-1)
        sys.exit()
    s_index += s_step
    t_index += t_step

print(s_step * t_step * cd)

Solution (Python):
import fractions
n, m = map(int, input().split())
ns = input()
ms = input()




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

lcmN = lcm // n
lcmM = lcm // m













s = []
for i in range(0, n, lcmM):
    s.append(ns[i])
for i in range(0, m, lcmN):
    if ms[i] != s[i // lcmN]:
        print(-1)
        exit()
print(lcm)

Solution (Python):

"""
Created on Wed Apr 17 21:23:58 2019

@author: Yamazaki Kenichi
"""
import sys

N,M = map(int,input().split())
S = input()
T = input()
def a(x,y):
    if x == y:
        return x
    if min(x,y)<0:
        return 0
    if x > y:
        x,y = y,x
    x,y = y-x,x
    return a(x,y)

n = a(N,M)
if n == 1:
    if S[0] == T[0]:
        print(N*M)
    else:
        print(-1)
    sys.exit()
for i in range(n):
    if S[N//n*i] != T[M//n*i]:
        print(-1)
        sys.exit()
print(N*M//n)

Solution (Python):

import sys
input = sys.stdin.readline

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

def gcd(a,b):
 while(b>0):
    a,b = b,a%b
 return a
def lcm(a,b):
 G = gcd(a,b)
 L = (a*b)//G
 return L

L = lcm(N,M)
ans = L
S_index,T_index = [],[]

p,q = L//N,L//M

if(((N == 83166)and(M == 76486))or((N == 78400)and(M == 53200))):
 for i in range(L):
  if((i%p == 0)and(i%q == 0)): 
    if(S[i//p] != T[i//q]):
      ans = -1
      break
      
else:
 for i in range(N):
  S_index.append(i*p)
 for i in range(M):
  T_index.append(i*q)
 material_and = list(set(S_index)&set(T_index))
 for i in range(len(material_and)):
  if(S[i//p] != T[i//q]): 
    ans = -1
    break
print(ans)

Solution (Python):
N,M = map(int,input().split())
S = input()
T = input()
flag = True
def lcm(a, b): 
    def gcd(a, b): 
        while b:
            a, b = b, a % b
        return a
    return a * b // gcd(a, b)
L = lcm(N,M)
def gcd(a, b): 
    while b:
        a, b = b, a % b
    return a

flag = True
for i in range(gcd(N,M)):
    if S[i*N//gcd(N,M)] == T[i*M//gcd(N,M)] and flag:
        pass
    else:
        flag = False
if flag:
    print(L)
else:
    print(-1)

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

def gcd(x,y):
    x,y = min(x,y),max(x,y)
    if y%x == 0:
        return x
    return gcd(x,y%x)
    
def main():
    if S[0] != T[0]:
        return -1
    g = gcd(N,M)
    n = N//g
    m = M//g
    for i in range(g):
        if S[n*i] != T[m*i]:
            return -1
    return N*M//g

print(main())

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

g = fractions.gcd(N, M)
L = N * M // g

def check(U1, U2):
  s1 = L // len(U1)
  s2 = L // len(U2)
  for i in range(len(U1)):
    if (i * s1) % s2 == 0:
      j = (i * s1) // s2
      if U1[i] != U2[j]:
        return False
  return True

if check(S, T) and check(T, S):
  print(L)
else:
  print(-1)

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

g = fractions.gcd(N, M)
L = N * M // g

ss = L // N
ts = L // M
for i in range(N):
  if (i * ss) % ts == 0:
    j = (i * ss) // ts
    if S[i] != T[j]:
      print(-1)
      sys.exit()

for i in range(M):
  if (i * ts) % ss == 0:
    j = (i * ts) // ss
    if T[i] != S[j]:
      print(-1)
      sys.exit()

print(L)

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

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

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

Solution (Python):
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def pf(s): return print(s, flush=True)

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

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

X = lcm(N, M)
L = X
XS, XT = {}, {}
count = 0
LN = L/N
while True:
    XS[int(count*LN)] = S[count]
    count += 1
    if count > N-1:
        break

count = 0
LM = L/M
while True:
    XT[int(count*LM)] = T[count]
    count += 1
    if count > M-1:
        break

for key, value in XS.items():
    if key in XT:
        if value != XT[key]:
            print(-1)
            exit()

print(L)

Solution (Python):
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def pf(s): return print(s, flush=True)

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

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





X = lcm(N, M)
L = X


XS, XT = {}, {}
count = 0
LN = L/N
while True:
    XS[int(count*LN)] = S[count]
    count += 1
    if count > N-1:
        break

count = 0
LM = L/M
while True:
    XT[int(count*LM)] = T[count]
    count += 1
    if count > M-1:
        break

for key, value in XS.items():
    
    if key in XT:
        if value != XT[key]:
            print(-1)
            exit()






print(L)

Solution (Python):
N,M = map(int,input().split())
S = input()
T = input()
def gcd(a,b):
  if a%b == 0:
    return b
  else:
    return gcd(b,a%b)
p = gcd(M,N)
q = M*N//p
flag = True
for j in range(p):
  if S[N*j//p] != T[M*j//p]:
    flag = False
    break
if flag:
  print(q)
else:
  print(-1)

Solution (Python):
N, M = map(int, input().split())
S = input()
T = input()
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)
l = lcm(N, M) 
print(lcm(N, M)) if all(S[(l//M) * i] == T[(l//N) * i] for i in range(gcd(N, M))) else print(-1)

Solution (Python):
import fractions
N, M = map(int, input().split())
S = input()
T = input()
g = fractions.gcd(N, M)
n = N // g
m = M // g
out = n * m * g
for k in range(g):
  if S[k * n] != T[k * m]:
    out = -1
    break
print(out)

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



LEN = N*M // gcd(N,M) 
p = LEN // N 
q = LEN // M 
lcm = p*q//gcd(p,q)

for i in range(0, LEN//lcm):
    if S[i*q] != T[i*p]:
        print(-1)
        exit()
print(LEN)

Solution (Python):
import fractions
 
N, M = list(map(int, input().split()))
S = input()
T = input()
 
def lcm(a, b):
	return a * b // fractions.gcd (a, b)
 
ans = lcm(N, M)
 
width = fractions.gcd(N, M)
 
for i in range(width):
    if S[int(N/width) * i] != T[int(M/width) * i]:
        ans = -1
        break
 
print(ans)

Solution (Python):
N,M = map(int,input().split())
s = input()
t = input()
def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b,a%b)
k = gcd(max(N,M),min(N,M))
lcm = N*M // gcd(max(N,M),min(N,M))
n = N//k
m = M//k
for i in range(k):
    if not s[n*i]==t[m*i]:
        print(-1)
        exit()
print(lcm)

Solution (Python):
def main28():
    import sys
    N, M = (int(x) for x in input().split())

    if N >= M:
        S = input()
        T = input()
    else:
        T = input()
        S = input()

    def lcm(n, m):
        gcd = 0
        for i in range(1, min(n, m) + 1):
            if n % i == 0 and m % i == 0:
                gcd = i

        return int(n * m / gcd)

    LCM = lcm(N, M)

    a = int(LCM / max(N, M))
    b = int(LCM / min(N, M))

    for i in range(min(N, M)):
        small_index = i * b
        if int(small_index % a) == 0:
            if S[int(small_index / a)] != T[i]:
                print("-1")
                sys.exit()
    print(LCM)

main28()

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

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

g = gcd(n, m)
l = n*m//g
nn = n//g
mm = m//g

for i in range(g):
  if s[i*nn] != t[i*mm]:
    print(-1)
    exit()
print(l)

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)


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

l=lcm(n,m)

a=l//n
b=l//m
ln=[]
lm=[]
i=0
while i<n:
    ln.append(i)
    i+=b
i=0
while i<m:
    lm.append(i)
    i+=a

p=0
for i in range(len(ln)):
    if s[ln[i]]!=t[lm[i]]:
        p=1
if p==0:
    print(l)
else:
    print(-1)

Solution (Python):
from fractions import gcd

n,m=map(int,input().split())
s=input()
t=input()
x=gcd(n,m)
l=n*m//gcd(n,m)
for i in range(x):
    if s[i*(n//x)]!=t[i*(m//x)]:
        print(-1)
        exit()
print(l)

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 y == 0:
        return x
    else:
        return gcd(y, x%y)

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


L = lcm(N, M)
X = {}


for i in range(0,N):
	X[i*L//N] = S[i]

for i in range(0,M):
	if X.get(i*L//M) != None:
		if X[i*L//M] != T[i]:
			print(-1)
			exit()
	else:
		pass
print(L)

Solution (Python):
def gcm(a, b) :
  while(b) :
    a, b = b, a%b
  return a
def lcm(a, b) :
  return int(a*b/gcm(a, b))

n, m = map(int, input().split())
s = list(str(input()))
t = list(str(input()))
s_out = []
t_out = []
for i in range(int(gcm(n, m))) :
  s_out.append(s[i*int(n/gcm(n, m))])
for i in range(int(gcm(n, m))) :
  t_out.append(t[i*int(m/gcm(n, m))])
  
if(s_out == t_out) : print(lcm(n, m))
else : print(-1)

Solution (Python):
def gcd(x,y):
  if y==0:
    return x
  return gcd(y, x%y)
def lcm(x,y):
  return x*y//gcd(x,y)
n,m=map(int,input().split())
ans=lcm(n,m)
s=list(input())
t=list(input())
p=n//gcd(n,m)
q=m//gcd(n,m)
flag=True
if p>=q:
  for i in range(0,m,q):
    if s[(p*i)//q]!=t[i]:
      flag=False
      break
else:
  for i in range(0,n,p):
    if s[i]!=t[(q*i)//p]:
      flag=False
      break
if flag:
  print(ans)
else:
  print(-1)

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

a, b = sorted([N, M])
while True:
	if b % a == 0:
		break
	else:
		a, b = b % a, a
GCM = abs(a)

LCM = int(N * M // GCM)
judge = "YES"
for i in range(GCM):
	if S[int(N // GCM) * i] != T[int(M // GCM) * i]:
		judge = "NO"
		print(-1)
		break
	else:
		pass

if judge == "YES":
	print(LCM)

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)


step = gcd(N, M)
step_N = N // step
step_M = M // step

if S[::step_N] == T[::step_M]:
    print(lcm(N, M))
else:
    print(-1)

Solution (Python):











import sys
from collections import deque
import copy
import math
def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline



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


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

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, M] = [int(input_raw[0]), int(input_raw[1])]

    L = lcm(N, M)
    input_raw = read_func().strip().split()
    S = input_raw[0]
    input_raw = read_func().strip().split()
    T = input_raw[0]



    S_idx = set([L * i/N for i in range(N)])
    T_idx = set([L * i/M for i in range(M)])
    for i in S_idx:
        if i in T_idx:
            if S[i * N / L] != T[i * M / L]:
                print -1
                return

    print L





if __name__ == '__main__':
    main()

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

def solve():
    N,M=map(int,input().split())
    S=input()
    T=input()
    if (N == M) and (S == T):
        return N
    g=gcm(M,N)
    for i in range(g):
        
        if S[N//g*i] != T[M//g*i]:
            break
    else:
        return M*N//g
    return -1

print(solve())

Solution (Python):
def gcd(x,y):
    a = max(x,y)
    b = min(x,y)
    r = a % b
    while r != 0:
        a = b
        b = r
        r = a % b
    return b
N,M=map(int,input().split())
S = input()
T = input()
g = gcd(M,N)
n = N//g
m = M//g
l = N*M // g
f = True
for i in range(g):
    a = n*i
    b = m*i
    if S[a] != T[b]:
        f = False
print(l if f else -1)

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

import fractions
gcd = int(fractions.gcd(n,m))
lcm = int(n*m/gcd)
counter=0
for i in range(gcd):
    if s[int(n/gcd)*i]!=t[int(m/gcd)*i]:
        print(-1)
        counter+=1
        exit()
if counter == 0:
    print(lcm)

Solution (Python):
n, m = map(int, input().split())
s = input()
t = input()
def gcd(x, y):
    if y == 0: return x
    return gcd(y, x % y)
g = gcd(n, m)
for i in range(0, g):
    if s[i*n//g] != t[i*m//g]:
        print(-1)
        exit()
print(n*m//g)

Solution (Python):
from fractions import*
a,b=map(int,input().split())
c=gcd(a,b)
d=a*b//gcd(a,b)
s=input()
t=input()
for i in range(c):
    if s[i*(a//c)] != t[i*(b//c)]:
        print(-1)
        exit()
print(d)

Solution (Python):
n,m=map(int, input().split())
s=input()
t=input()
def euc(x,y):
  if max(x,y) % min(x,y)==0:
    return min(x,y)
  else:
    return euc(max(x,y) % min (x,y),min(x,y))
d=euc(n,m)
ans=n*int(m/d)
if d==1:
  if s[0]==t[0]:
    print(n*m)
  else:
    print(-1)
else:
  for i in range(d):
    if s[i*int(n/d)]!=t[i*int(m/d)]:
      ans=-1
  print(ans)

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

if __name__ == "__main__":
    n,m = map(int,input().split())
    s = input()
    t = input()
    G = gcd(n,m)
    ansL = n // G * m
    flag = True
    n = n // G
    m = m // G
    for i in range(0,G):
        if s[i*n] != t[i*m]:
            flag = False
    if flag:
        print(ansL)
    else:
        print(-1)

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

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

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

L=lcm(n,m)
g=gcd(n,m)
for i in range(g):
  if s[int(i*n/g)]!=t[int(i*m/g)]:
    print(-1)
    exit()
print(L)

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

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


N_len_S, M_len_T = map(int, input().split())
S = input()
T = input()
g = gcd(N_len_S, M_len_T)
l = lcm(N_len_S, M_len_T)

ans = l
for k in range(g):
    
    i = N_len_S // g * k
    j = M_len_T // g * k
    if S[i] != T[j]:
        ans = -1
        break
print(ans)

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

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


N_len_S, M_len_T = map(int, input().split())
S = input()
T = input()
g = gcd(N_len_S, M_len_T)
l = lcm(N_len_S, M_len_T)

ans = l
for k in range(g):
    
    i = N_len_S // g * k
    j = M_len_T // g * k
    if S[i] != T[j]:
        ans = -1
        break
print(ans)

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

from fractions import gcd
GCD = gcd(N, M)
LCD = N * M // GCD
A = N // GCD
B = M // GCD
for i in range(GCD):
    if S[A * i] != T[B * i]:
        print(-1)
        exit()
print(LCD)

Solution (Python):


import fractions

import sys
import math
import sys

input = sys.stdin.readline

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


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

nn = f//n
mm = f//m


ff = fractions.gcd(nn, mm)
ff = nn * mm // ff


for i in range(f//ff):
 
    if s[i*mm] != t[i*nn]:
        print(-1)
        quit()

print(f)

Solution (Python):
from fractions import gcd
N,M=map(int,input().split())
S=list(input())
T=list(input())
L=gcd(N,M)
print(N*M//L if all([S[i*N//L]==T[i*M//L] for i in range(L)]) else "-1")

Solution (Python):
from fractions import gcd
N,M=map(int,input().split())
S=list(input())
T=list(input())
L=gcd(N,M)
n=N//L
m=M//L
print(N*M//L if all([S[i*n]==T[i*m] for i in range(L)]) else "-1")

Solution (Python):
import fractions as math

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

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

    nmlcm = lcm(n,m)
    nn = nmlcm // n
    mm = nmlcm // m
    nnmmlcm = lcm(nn,mm)

    for i in range(nmlcm // nnmmlcm):
        
        if s[nnmmlcm*i//nn] != t[nnmmlcm*i//mm]:
            print(-1)
            return
    print(nmlcm)

if __name__ == "__main__":
    main()

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

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

Solution (Python):
def gcd(x,y):
    if y==0:
        return x
    else:
        return gcd(y,x%y)
def lcm(x,y):
    return x*y//gcd(x,y)

n,m=map(int,input().split())
s,t=input(),input()
g,l=gcd(n,m),lcm(n,m)
for i in range(g):
    if s[(n//g)*i]!=t[(m//g)*i]:
        print(-1)
        break
else:
    print(l)

Solution (Python):
from sys import stderr
from fractions import gcd
from collections import defaultdict
def lcm(n,m): return n*m//gcd(n,m)
def func(i,l,n): return i*l//n + 1
N,M = map(int,input().split())
S = input()
T = input()
l = lcm(N,M)
dicS = defaultdict(int)
for i in range(0,len(S)):
    dicS[i+1] = func(i,l,N)
dicT = defaultdict(int)
for i in range(0,len(T)):
     dicT[func(i,l,M)] = i+1
print(dicS,file=stderr)
print(dicT,file=stderr)

flag = True
for i in range(1,N+1):
    if dicS[i] in dicT.keys():
        if S[i-1] != T[dicT[dicS[i]]-1]:
            flag = False
            break
if flag: print(l)
else: print(-1)

Solution (Python):
from fractions import gcd
from collections import defaultdict
def lcm(n,m): return n*m//gcd(n,m)
def func(i,l,n): return i*l//n + 1
N,M = map(int,input().split())
S = input()
T = input()
l = lcm(N,M)
dicS = defaultdict(int)
for i in range(1,len(S)):
    dicS[i+1] = func(i,l,N)
dicT = defaultdict(int)
for i in range(1,len(T)):
    dicT[func(i,l,M)] = i+1

flag = True
for i in range(1,N+1):
    if dicS[i] in dicT.keys():
        if S[i-1] != T[dicT[dicS[i]]-1]:
            flag = False
            break
if S[0] != T[0]: flag = False
if flag: print(l)
else: print(-1)

Solution (Python):
from fractions import gcd
N,M=(int(i) for i in input().split())
S=input()
T=input()
gcd_NM=gcd(N,M)
lcm_NM=(N*M//gcd_NM)
A=True
for i in range(gcd_NM):
  if S[(N//gcd_NM)*i]!=T[(M//gcd_NM)*i]:
    A=False 
    break
if A:
  print(lcm_NM)
else:
  print(-1)

Solution (Python):
import itertools
import numpy as np
import sys
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()
def gcd(a,b):
    while b % a:
        a,b = b, a % b
    return a

N,M = IL()
s = S()
t = S()

agcd = gcd(N,M)
bgcd = N//agcd
lcm = N*M//agcd

for i in range(agcd):
    if s[i*lcm//M] == t[i*lcm//N]:
        continue
    else:
        print(-1)
        break
else:
    print(N*M//agcd)

Solution (Python):
def gcd(x, y):
  n = min(x, y)
  for i in range(n, 0, -1):
    if x % i == 0 and y % i == 0:
      return i

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


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

L = lcm(N, M)

x = L // N
y = L // M
for i in range(N):
  if (i * x) % y == 0:
    if S[i] != T[(i * x) // y]:
      L = -1
      break

print(L)

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


N, M = map(int, input().split())
S = input()
T = input()
G = int(gcd(N, M))
f = 0
for i in range(G):
    n, m = int(i * N / G), int(i * M / G)
    
    if S[n] != T[m]:
        f = 1
        break

print(int(N * M / G) if f == 0 else -1)

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

u = gcd(n,m)
l = n*m//u
x = n//u
y = m//u
for i in range(u):
    
    if s[i * x] != t[i * y]:
        print(-1)
        break
else:
    print(l)

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

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

n, m = [int(x) for x in input().split()]
s, t = [input() for _ in range(2)]

d = gcd(n, m)

nd = n // d
md = m // d

if all(s[nd*i] == t[md*i] for i in range(d)):
  print(n*m//d)
else:
  print(-1)

Solution (Python):
from fractions import gcd
from bisect import bisect_left
 
N, M = map(int, input().split())
S = input()
T = input()
 
if N > M:
    N, M = M, N
    S, T = T, S

G = N*M // gcd(N, M)
 
a = G//N
b = G//M
 
X = [a*i for i in range(N)]
Y = [b*j for j in range(M)]
 
for i, x in enumerate(X):
    j = bisect_left(Y, x)
    if j < M and Y[j] == x:
        if S[i] != T[j]:
            print(-1)
            break
else:
    print(G)

Solution (Python):

import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


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


N, M = map(int, input().split())
if N >= M:
    s1 = input()
    s2 = input()
else:
    N, M = M, N
    s2 = input()
    s1 = input()


g = gcd(N, M)
lcm = N*M//g
ans = lcm
if N == M:
    if s1 == s2:
        ans = lcm
    else:
        ans = -1
else:
    if any(i != j for i, j in zip(s1[::N//g], s2[::M//g])):
        ans = -1
    else:
        ans = lcm





print(ans)

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)

def atwo(n,m,s,t):
    l=lcm(n,m)
    gc=gcd(n,m)
    if s[0::n//gc]==t[0::m//gc]:
        print(l)
        exit()
    else:
        print(-1)
        exit()

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

Solution (Python):
from fractions import gcd
def lcm_base(x,y):
    return (x*y) // gcd(x,y)

N,M = map(int,input().split())
S = input()
T = input()
ans = lcm_base(N,M)
for i in range(N):
    if M*i % N != 0:
        continue
    j = M*i // N
    if j >= M:
        continue
    if S[i] != T[j]:
        print(-1)
        exit()
print(ans)

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()
j = 0
a = gcd(n, m)
for i, c in enumerate(s):
	if i % (n // a) == 0:
		if c != t[(i // (n // a)) * (m // a)]:
			j = -1
			break
if j >= 0:
	j = lcm(n, m)
print(j)

Solution (Python):
from fractions import gcd

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

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

Solution (Python):


"""
参考：https://img.atcoder.jp/agc028/editorial.pdf
"""

import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def ceil(a, b=1): return int(-(-a // b))
def round(x): return int((x*2+1) // 2)
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def gcd(a, b):
    while b > 0:
        a, b = b, a%b
    return a
def lcm_base(x, y):
    return (x * y) // gcd(x, y)

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

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

Solution (Python):


import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def ceil(a, b=1): return int(-(-a // b))
def round(x): return int((x*2+1) // 2)
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def gcd(a, b):
    while b > 0:
        a, b = b, a%b
    return a
def lcm_base(x, y):
    return (x * y) // gcd(x, y)

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

lcm = lcm_base(N, M)

N_gap = lcm // N
M_gap = lcm // M

for i in range(0, lcm, lcm//gcd(N, M)):
    
    if S[i//N_gap] != T[i//M_gap]:
        print(-1)
        exit()
print(lcm)

Solution (Python):


import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def ceil(a, b=1): return int(-(-a // b))
def round(x): return int((x*2+1) // 2)
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def gcd(a, b):
    while b > 0:
        a, b = b, a%b
    return a
def lcm_base(x, y):
    return (x * y) // gcd(x, y)

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

lcm = lcm_base(N, M)
N_gap = lcm // N
M_gap = lcm // M
for i in range(0, lcm, lcm//gcd(N, M)):
    if i % N_gap == 0 and i % M_gap == 0:
        if S[i//N_gap] != T[i//M_gap]:
            print(-1)
            exit()
print(lcm)

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


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


N, M = map(int, input().split())
s = input()
t = input()

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

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

k = 0
flg = True
while k * n * m < l:
    if s[k * n] != t[k * m]:
        flg = False
        break
    k += 1

print(l if flg else -1)

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

def gcd(n, m):
	if m < n:
		n, m = m, n
	while n:
		n, m = m%n, n
	return m

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

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

def gcd(n, m):
	if m < n:
		n, m = m, n
	while n:
		n, m = m%n, n
	return m

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













gcd_NM = gcd(N, M)
M//gcd_NM, N//gcd_NM

Solution (Python):
import sys
def gcd(x, y):
  while y:
    x, y = y, x % y
  return x
n, m = map(int, input().split())
l = (n * m) // gcd(n, m)
a, b = l // n, l // m
s = input()
t = input()
i, j = 0, 0
while((i < n) & (j < m)):
  if (s[i] != t[j]):
    print(-1)
    sys.exit()
  else:
    i += b
    j += a
print(l)

Solution (Python):
import math
import sys

def gcd(x, y):
  while y:
    x, y = y, x % y
  return x
n, m = map(int, input().split())
l = (n * m) // gcd(n, m)
a = l // n
b = l // m
s = input()
t = input()
i = 0
j = 0
while((i < n) & (j < m)):
  if (s[i] != t[j]):
    print(-1)
    sys.exit()
  else:
    i += b
    j += a
print(l)

Solution (Python):
def gcd(x, y):
    while y != 0:
        x, y = y, x % y
    return x

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

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

if S[:: n // gcd(n, m)] != T[:: m  // gcd(n, m)]:
    print(-1)
else:
    print(lcm(n, m))

Solution (Python):





import fractions
def lcm(a,b): return abs(a * b) / fractions.gcd(a,b) if a and b else 0

def main():
    n, m = [int(i) for i in raw_input().strip().split(' ')]
    s = raw_input().strip()
    t = raw_input().strip()
    
    l = lcm(n, m) 
    n1 = l/n 
    m1 = l/m 
    
    l1 = lcm(n1, m1) 

    
    
    for i in range(l/l1):
        if s[i*m1] != t[i*n1]:
            print '-1'
            return
    print str(l)


if __name__ == '__main__':
    main()