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 heapq import heappush,heappop,heapify
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
import math
import time
import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def ItoS(nn):
    return chr(nn+97)
def LtoS(ls):
    return ''.join(chr(i+97) for i in ls)
def GI(V,E,Directed=False,index=0):
    org_inp=[]
    g=[[] for i in range(n)]
    for i in range(E):
        inp=LI()
        org_inp.append(inp)
        if index==0:
            inp[0]-=1
            inp[1]-=1
        if len(inp)==2:
            a,b=inp
            g[a].append(b)
            if not Directed:
                g[b].append(a)
        elif len(inp)==3:
            a,b,c=inp
            aa=(inp[0],inp[2])
            bb=(inp[1],inp[2])
            g[a].append(bb)
            if not Directed:
                g[b].append(aa)
    return g,org_inp
def bit_combination(k,n=2):
    rt=[]
    for tb in range(n**k):
        s=[tb//(n**bt)%n for bt in range(k)]
        rt+=[s]
    return rt
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')
l_alp=string.ascii_lowercase
u_alp=string.ascii_uppercase
ts=time.time()

input=lambda: sys.stdin.readline().rstrip()

def ran_input():
    import random
    n=random.randint(4,16)
    rmin,rmax=1,10
    a=[random.randint(rmin,rmax) for _ in range(n)]
    return n,a

show_flg=False
show_flg=True

ans=inf

n,m=LI()
s=input()
t=input()
import fractions
g=fractions.gcd(n,m)

a,b=n//g,m//g

if s[::a]==t[::b]:
    print(n*m//g)
else:
    print(-1)

Solution (Python):
import fractions as f
n,m=map(int,input().split())
s=list(input())
t=list(input())
ans=0
N=n//f.gcd(n,m)
M=m//f.gcd(n,m)
for i in range(f.gcd(n,m)):
    if s[i*N]!=t[i*M]:
        ans=-1
        break
if ans!=-1:
    print(n*m//f.gcd(n,m))
else:
    print(-1)

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

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

from fractions import gcd

N,M = map(int,readline().split())
S = readline().rstrip().decode('utf-8')
T = readline().rstrip().decode('utf-8')

G = gcd(N,M)



A = ''.join(S[::N//G])
B = ''.join(T[::M//G])

if A == B:
    answer = N * M // G
else:
    answer = -1
print(answer)

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

N,M=map(int,input().split())
S=input()
T=input()
L=N*M//gcd(N,M)
n=L//N
m=L//M
l=n*m//gcd(n,m)
i=l//n
j=l//m
for k in range(N//i):
    if S[i*k]==T[j*k]:
        continue
    else:
        print(-1)
        sys.exit()
print(L)

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

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

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

Solution (Python):
"""a,bの最大公約数"""
def gcd(a,b):
    while b!=0:
        a,b=b,a%b
    return a


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)
        exit()
print(n*m//g)

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

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

Solution (Python):
N,M = map(int,input().split())
def gcd(a,b):
    if a >= b:
        if b == 0:
            return a
        else:
            return gcd(b,a%b)
    else:
        if a == 0:
            return b
        else:
            return gcd(a,b%a)
S = input()
T = input()
if S[0] != T[0]:
    print(-1)
else:
    flag = True
    L = int((N//gcd(N,M))*M)
    m = L//M
    n = L//N
    for i in range(max(N,M)):
        if i*m <= N-1 and i*n <= M-1:
            if S[i*m] != T[i*n]:
                flag = False
                break
    if flag:
        print(L)
    else:
        print(-1)

Solution (Python):
import fractions as f
n,m=map(int,input().split())
s=list(input())
t=list(input())
ans=0
N=n//f.gcd(n,m)
M=m//f.gcd(n,m)
for i in range(f.gcd(n,m)):
    if s[i*N]!=t[i*M]:
        ans=-1
        break
if ans!=-1:
    print(n*m//f.gcd(n,m))
else:
    print(-1)

Solution (Python):
def gcd(x,y):
    while y>0:
        x,y = y,x%y
    return x
N,M = map(int,input().split())
S = input().strip()
T = input().strip()
a = gcd(N,M)
L = (N//a)*(M//a)*a
ks = L//N
kt = L//M
flag = 0
if S[0]!=T[0]:
    flag = 1
else:
    b = gcd(ks,kt)
    kl = (ks//b)*(kt//b)*b
    for i in range(min(N,M)):
        if (kl//ks)*i<N and (kl//kt)*i<M and S[(kl//ks)*i]!=T[(kl//kt)*i]:
            flag = 1
            break
if flag==1:
    print(-1)
else:
    print(L)

Solution (Python):
import sys
n, m = [int(i) for i in sys.stdin.readline().split()]
s = input()
t = input()

def gcd(a, b):
    while a and b:
        if a < b:
            b %= a
        else:
            a %= b
    return max(a, b)

_gcd = gcd(n, m)
if s[::n // _gcd] == t[::m // _gcd]:
    print(n * m // _gcd)
else:
    print(-1)

Solution (Python):
from fractions import gcd
from sys import exit, stdin
N, M = [int(_) for _ in stdin.readline().rstrip().split()]
S = stdin.readline().rstrip()
T = stdin.readline().rstrip()

def lcm(x, n, m):
    return x // gcd(n, m)
  
lcm_n, lcm_m = lcm(N, N, M), lcm(M, N, M)

if S[::lcm_n] != T[::lcm_m]:
    print(-1)
    exit()
print(lcm((N*M), N, M))

Solution (Python):
from fractions import gcd


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


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

if s[::int(lcm/m)]!=t[::int(lcm/n)]:
    print(-1);exit()

print(lcm)

Solution (Python):
from fractions import gcd
def lcm(x,y):return (x*y)//gcd(x,y)
n,m=map(int,input().split())
s,t=input(),input()
lcm=lcm(n,m)
if s[::int(lcm/m)]!=t[::int(lcm/n)]:print(-1);exit()
print(lcm)

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)
S=[(i,int(i*(lcm/n)+1)) for i in range(n)]
L=[(i,int(i*(lcm/m)+1)) for i in range(m)]
left,right=0,0
ans=[]
while left!=n and right!=m:
    if S[left][1]==L[right][1]:
        ans.append([S[left][0],L[right][0]])
        right +=1
        left +=1
    elif S[left][1]>L[right][1]:
        right +=1
    elif S[left][1]<L[right][1]:
        left +=1
for l,r in ans:
    if s[l]==t[r]:continue
    else:print(-1);exit()
print(lcm)

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

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

for i in range(N) :
  if i * M % N != 0 :
    continue
  if S[i] != T[i * M // N] :
    print(-1)
    break
else :
  print(lcm(N, M))

Solution (Python):
from fractions import gcd
import sys
input = sys.stdin.readline

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)
        exit()
print(l)

Solution (Python):
import fractions

N,M=map(int,input().split())
g=fractions.gcd(N,M)

a=N//g;b=M//g

S=input();T=input()

f=True
for k in range(g):
    if S[k*a]!=T[k*b]:
        f=False
        break

print(a*b*g if f else -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

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

L = lcm(N, M)
s = L // M
t = L // N

if S[::s] != T[::t]:
    L = -1
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

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

L = lcm(N, M)
s = L // M
t = L // N

if S[::s] != T[::t]:
    L = -1
print(L)

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

D = [N, M]
while D[1] != 0:
  D[0], D[1] = D[1], D[0] % D[1]
R = D[0]
L = R * (N // R) * (M // R)
E = L
for i in range(R):
  if S[i * (L // M)] != T[i * (L // N)]:
    E = -1
print(E)

Solution (Python):
import fractions

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

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

if s[0] != t[0]:
    print(-1)
    exit()
    
l = lcm(n, m)
k = lcm(l//n, l//m)

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

Solution (Python):
import fractions
N, M = map(int, input().split())
S = input()
T = input()
ans = (N * M) // fractions.gcd(N, M)
n = N // fractions.gcd(N, M)
m = M // fractions.gcd(N, M)
for i in range(min(N // n, M // m)):
    tmpn = S[n * i]
    tmpm = T[m * i]
    if tmpn != tmpm:
        ans = -1
        break

print(ans)

Solution (Python):

import sys

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():
    n, m = map(int, sys.stdin.readline().split())
    s, t = sys.stdin.read().split()

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

    for i in range(g):
        if s[i * n // g] == t[i * m // g]:
            continue
        ans = -1
        break
    else:
        ans = l
    
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):

import sys

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():
    n, m = map(int, sys.stdin.readline().split())
    s, t = sys.stdin.read().split()

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

    if g == 1:
        if s[0] == t[0]:
            ans = l
        else:
            ans = -1
    else:
        for i in range(g):
            if s[i * n // g] == t[i * m // g]:
                continue
            else:
                ans = -1
                break
        else:
            ans = l
    
    print(ans)

if __name__ == '__main__':
    main()

Solution (Python):

from heapq import heappush, heappop, heapify
from collections import deque, defaultdict, Counter
import itertools
from itertools import permutations, combinations
import sys
import bisect
import string
import math
import time
from fractions import gcd



def I(): return int(input())


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


def MS(): return map(str, input().split())


def LI(): return [int(i) for i in input().split()]


def LI_(): return [int(i)-1 for i in input().split()]


def StoI(): return [ord(i)-97 for i in input()]


def ItoS(nn): return chr(nn+97)


def input(): return sys.stdin.readline().rstrip()


def show(*inp, end='\n'):
    if show_flg:
        print(*inp, end=end)


YN = ['Yes', 'No']
MOD = 10**9+7
inf = float('inf')
l_alp = string.ascii_lowercase
u_alp = string.ascii_uppercase
ts = time.time()
sys.setrecursionlimit(10**6)



show_flg = True


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


def coprime(a, b):
    return gcd(a, b) == 1


def main():
    N, M = MI()
    S = input()
    T = input()

    LMC = lcm(N, M)

    if S[0] != T[0]:
        print(-1)
    else:
        a = LMC / N
        b = LMC / M
        abl = lcm(a, b)
        cur = 1
        while True:
            i = int(cur * abl * N // LMC)
            j = int(cur * abl * M // LMC)

            

            if i >= N or j >= M:
                break

            if S[i] != T[j]:
                print(-1)
                return
            cur += 1

        print(LMC)


if __name__ == '__main__':
    main()

Solution (Python):
import fractions
n,m=map(int,input().split())
s=str(input())
t=str(input())
f=fractions.gcd(n,m)
f2=n*m//f

for i in range(f2,n*m+1,f2):
    z2=(i//n)*(i//m)//fractions.gcd(i//n,i//m)
    for j in range(1,i+1,z2):
        
        if s[-(-j//(i//n))-1]!=t[-(-j//(i//m))-1]:
            break
    else:
        print(i)
        break
else:
    print(-1)

Solution (Python):
import fractions
N, M = map(int, input().split())
S = input()
T = input()
ans = (N * M) // fractions.gcd(N, M)
n = N // fractions.gcd(N, M)
m = M // fractions.gcd(N, M)
for i in range(min(N // n, M // m)):
    tmpn = S[n * i]
    tmpm = T[m * i]
    if tmpn != tmpm:
        ans = -1
        break

print(ans)

Solution (Python):
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.readline
readlines = sys.stdin.buffer.readlines

N, M = map(int, readline().split())
S = readline()
T = readline()
S = list(S.rstrip())
T = list(T.rstrip())
def gcd(a, b):
    while b:
        a, b = b, a%b
    return a

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

if S[::y] != T[::x]:
    print(-1)
    exit()
print(l)

Solution (Python):
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.readline
readlines = sys.stdin.buffer.readlines

N, M = map(int, readline().split())
S = readline()
T = readline()
S = list(S.rstrip())
T = list(T.rstrip())
def gcd(a, b):
    while b:
        a, b = b, a%b
    return a

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

for i,s in enumerate(S[::y]):
    if s != T[x*i]:
        print(-1)
        exit()
print(l)

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

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

N,M = map(int,input().split())
S = input()
T = input()
g = gcd(N,M)
N1 = N//g
M1 = M//g

bl = True
for i,s in enumerate(S[::N1]):
    if s != T[M1*i]:
        bl = False
        break

answer = N * M1 if bl else -1
print(answer)

Solution (Python):
import fractions

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

Solution (Python):
import bisect
import heapq
import itertools
import math
import operator
import os
import re
import string
import sys
from collections import Counter, deque, defaultdict
from copy import deepcopy
from decimal import Decimal
from fractions import gcd
from functools import lru_cache, reduce
from operator import itemgetter, mul, add, xor

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7



N, M = list(map(int, sys.stdin.buffer.readline().split()))
S = sys.stdin.buffer.readline().decode().rstrip()
T = sys.stdin.buffer.readline().decode().rstrip()

g = gcd(N, M)
ok = True
for c, d in zip(S[::N//g], T[::M//g]):
    ok &=c == d
if ok:
    print(N*M//g)
else:
    print('-1')

Solution (Python):
from fractions import gcd
n,m=map(int,input().split())
s=input()
t=input()
p=gcd(n,m)
ans=n*m//p 
for i in range(n):
	if abs((i*(ans//n)/(ans//m))-int(i*(ans//n)/(ans//m)))<=10**(-7):
		if s[i]==t[(i*(ans//n)//(ans//m))]:
			continue
		else:
			print(-1)
			exit()
print(ans)

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()
l = lcm(N, M)
if S[0] != T[0]:
    print(-1)
    exit()
if N == 1 or M == 1:
    if N == 1:
        print(M)
    if M == 1:
        print(N)
    exit()

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

G = gcd(N, M)
if G != 1:
    for g in range(G):
        if S[g * N // G] == T[g * M // G]:
            pass
        else:
            print(-1)
            exit()
print(l)

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

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

l = lcm(n, m)
x, y = l // n, l // m

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

Solution (Python):
import fractions
import bisect

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

A=(N//fractions.gcd(N,M))*M

NL=[0]*N
ML=[0]*M

for i in range(N):
    NL[i]=i*(A//N)


for i in range(M):
    ML[i]=i*(A//M)


ANDL = sorted(list(set(NL) & set(ML)))

for i in ANDL:
    St=bisect.bisect_left(NL,i)
    Tt=bisect.bisect_left(ML,i)
    if(S[St]!=T[Tt]):
        print("-1")
        exit()
print(A)

Solution (Python):

import fractions

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


if N == M:
    l = -1
    if S == T:
        l = N
else:
    if N > M:
        w_n, w_m = N, M
        w_s, w_t = S, T
    else:
        w_n, w_m = M, N
        w_s, w_t = T, S

    if w_n % w_m == 0:
        k = w_n // w_m
        is_ok = True
        l = len(w_s)
        for i, char in enumerate(w_t):
            if S[(i - 1) ** k] != char:
                is_ok = False
                break
        if not is_ok:
            l = -1
    else:
        
        l = w_m * w_n // fractions.gcd(w_m, w_n)
        is_ok = True
        s_idx_list = []
        t_idx_list = []

        
        for i in range(w_n):
            s_idx_list.append(i * (l // w_n))
            t_idx_list.append(i * (l // w_m))
        common_idx_list = list(set(s_idx_list) & set(t_idx_list))

        for j in common_idx_list:
            s_idx = w_n * j // l
            t_idx = w_m * j // l
            if t_idx > w_m - 1:
                break
            if w_s[s_idx] != w_t[t_idx]:
                is_ok = False
                break
        if not is_ok:
            l = -1

ans = l

print(ans)

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

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

k=N*M//gcd(N,M)
X=[0]*N
for i,s in enumerate(S):
  X[i]=s
  
for i,t in enumerate(T):
  if (i*k//M)%(k//N)!=0:
    pass
  elif (i*k//M)%(k//N)==0 and X[(i*k//M)//(k//N)]==t:
    pass
  else:
    print(-1)
    exit()
    
print(k)

Solution (Python):
n,m=map(int,input().split())
s=input()
t=input()
from fractions import gcd
def lcm(x,y):
  return (x*y)//gcd(x,y)
g=gcd(n,m)
a=n//g;b=m//g
x=lcm(n,m)
for i in range(g):
  if s[a*i]!=t[b*i]:
    x=-1
    break
print(x)

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 = map(int, input().split())
s = input()
t = input()

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

lcm_ = lcm(N, M)

x = 0
while x * n < N and x * m < M:
    if s[x * n] != t[x * m]:
        print(-1)
        exit()
    x += 1
print(lcm_)

"""
0-indexedで考える。
s : x[0], x[k*L/N], x[k*L/N*2], ...
t : x[0], x[k*L/M], x[k*L/M*2], ...
同じindexを指しているとき、同じ文字である必要がある。

len(x)はlcm(N,M)の倍数。

N = gn
M = gm
L = gnm = NM/g

s : x[0], x[k*M/g], x[k*M/g*2], ... x[k*M/g*a], ...
t : x[0], x[k*N/g], x[k*N/g*2], ... x[k*N/g*b], ...

k*M/g*a==k*N/g*b

kにかかわらず
if ma==nb:
    
    if s[a] != t[b]:
        return False
"""

Solution (Python):
from fractions import gcd


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

    g = gcd(n, m)

    def f(x):
        ret = ""
        for i in range(0, len(x), len(x) // g):
            ret += x[i]

        return ret

    if f(s) == f(t):
        ans = n * m // g
    else:
        ans = -1

    print(ans)


if __name__ == "__main__":
    main()

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


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


st = gcd(s, t)
good = s * t // st

if S[::s // st] == T[::t // st]:
    print(good)
else:
    print(-1)

Solution (Python):
from fractions import gcd

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

st = gcd(s, t)
good = s * t // st

if S[::s // st] == T[::t // st]:
    print(good)
else:
    print(-1)

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):
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 = map(int,input().split())
s=list(input())
t=list(input())
l=lcm(n,m)
g=gcd(n,m)
for i in range(g):
    if s[i*(n//g)]!=t[i*(m//g)]:
        l=-1
        break
print(l)

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

if s[0]!=t[0]:
    print(-1)
    exit()

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

num=gcd(n,m)

if num==1:
    ans=n*m

else:
    ans=n*m//num
    check1=n//num
    check2=m//num
    for i in range(1,num):
        if s[i*check1]==t[i*check2]:
            continue
        else:
            print(-1)
            exit()
print(ans)

Solution (Python):
from fractions import gcd

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

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

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

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

print(lcm(N, M))

Solution (Python):
m, n = [ int(v) for v in input().split() ]
s = input()
t = input()


def gcd(a,b):
    if a < b:
        a, b = b, a
    while b >= 1:
        a, b = b, a % b
    return a
def lcm(a,b):
	return a * b // gcd(a,b)

g = gcd(m,n)

ds = [ v  for i, v in enumerate(s) if i % (m/g) == 0 ]
dt = [ v  for i, v in enumerate(t) if i % (n/g) == 0 ]
print( lcm(m,n) if ds == dt else -1 )

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

def gcd(x, y):
    while x != 0 and y != 0:
        x, y = min(x,y), max(x,y)
        y %= x
    return x

def aa():
    a = gcd(n, m)
    ss = n // a
    tt = m // a
    si = 0
    ti = 0
    for i in range(a):
        if s[si] != t[ti]:
            return -1
        si += ss
        ti += tt
    return n * m // a
print(aa())

Solution (Python):
import sys
sys.setrecursionlimit(10 ** 7)


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


def main():
    n, m = map(int, input().split())
    s = input()
    t = input()
    g = gcd(n, m)
    n1 = n // g
    m1 = m // g

    b = True
    for i, v in enumerate(s[::n1]):
        if v != t[m1*i]:
            b = False
            break
    print(n * m1 if b else -1)


if __name__ == '__main__':
    main()

Solution (Python):
def gcd(a, b):
    """a, bの最大公約数(greatest common divisor:GCD)を求める"""
    if b == 0:
        return a
    return gcd(b, a%b)


def lcm(a, b):
    """a, bの最小公倍数(least common multiple:LCM)を求める"""
    return (a * b) // gcd(a, b)


n, m = map(int, input().split())
s = input()
t = input()
gcd_nm = gcd(n, m)
s_num = n // gcd_nm
t_num = m // gcd_nm

for i in range(gcd_nm):
    if s[i*s_num] == t[i*t_num]:
        continue
    else:
        print(-1)
        break
else:
    print(lcm(n, m))

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[i*n//g] != t[i*m//g]:
        print(-1)
        break
else: print(l)

Solution (Python):
import collections
import fractions
N, M = map(int, input().split())
S = input()
T = input()
lcm = (N*M) // fractions.gcd(N, M)
if S[0] != T[0]:
    print(-1)
elif N == M and S != T:
    print(-1)
else:
    tmp = lcm // N
    tmp2 = lcm // M
    tmp_s = collections.defaultdict(str)
    for i in range(N):
        tmp_s[tmp*i] = S[i]

    for i in range(M):
        if tmp2*i in tmp_s:
            if T[i] != tmp_s[tmp2*i]:
                print(-1)
                exit(0)
    print(lcm)

Solution (Python):
from collections import Counter,defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))


n,m = inpl()
s = list(input())
t = list(input())
if n < m:
    n,m = m,n
    s,t = t,s
ggg = n*m//fractions.gcd(n,m)
tn = ggg//n
tm = ggg//m
i = 0
while i*tm < n and i*tn < m:
    if s[i*tm] != t[i*tn]:
        print(-1)
        break
    i += 1
else:
    print(ggg)

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

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

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

def lcm(N, M):
    return N * M // gcd(N, M)

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



ans = True
for i in range(0, L, C):
    s = S[i // n]
    t = T[i // m]
    if s != t:
        ans = False
        break

if ans:
    print(L)
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
g=gcd(N,M)
L=N*M//g
if all(S[i*N//g]==T[i*M//g]for i in range(g)):
  print(L)
else:
  print(-1)

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


def euclid(x, y):
    x, y = max(x, y), min(x, y)
    if y == 0:
        return x
    return euclid(y, x % y)


lcm = n * m // euclid(n, m)
nn = lcm // n
mm = lcm // m
ss = s[0::mm]
tt = t[0::nn]

if ss == tt:
    print(lcm)
else:
    print(-1)

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

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

Solution (Python):
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda :sys.stdin.readline().rstrip()
def resolve():
    from fractions import gcd
    n,m=map(int,input().split())
    s,t=[input() for _ in range(2)]
    gcd=gcd(n,m)
    lcm=n*m//gcd
    n//=gcd
    m//=gcd
    print(lcm if all(s[n*i]==t[m*i] for i in range(gcd)) else -1)
resolve()

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


if N < M:
    S, T = T, S
    N, M = M, N

for j, t in enumerate(T):
    if j * N % M == 0:
        k = j * N // M
        s = S[k]
        if t != s:
            print('-1')
            exit()

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

GCD = gcd(N, M)
LCM = N * M // GCD

print(LCM)

Solution (Python):
N,M=map(int,input().split())
S=input()
T=input()
from fractions import gcd
g=gcd(N,M)
r=1
j,k=0,0
for i in range(g):
    if S[j]!=T[k]:
        r=0
    j+=N//g
    k+=M//g
print(M*N//g if r else -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()

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

IsOk = True
for i in range(gcd(N, M)):
  if S[n * i] != T[m * i]:
    IsOk = False

if IsOk:
  print(lcm(N, M))
else:
  print(-1)

Solution (Python):
import fractions
N,M = map(int,input().split())
S = input()
T = input()
G = fractions.gcd(N,M)
L = (N * M) // G
div_N = N // G
div_M = M // G

i = 0
j = 0

while i < N and j < M:
  if S[i] != T[j]:
    print(-1)
    exit()
  else:
    i += div_N
    j += div_M
print(L)

Solution (Python):
import sys
from collections import defaultdict
sys.setrecursionlimit(200000)
input = sys.stdin.readline

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

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

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


m = {}

for i in range(N):
    m[i * (l // N)] = S[i]

for i in range(M):
    index = i * (l // M)
    if m.get(index) == None:
        m[index] = T[i]
    elif m[index] == T[i]:
        pass
    else:
        print(-1)
        exit()

print(l)

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

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

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

g = gcd(N, M)
i, j = 0, 0
ok = True
while i < N and j < M:
  if S[i] != T[j]:
  	ok = False
  i += N // g
  j += M // g
if ok:
  print(lcm(N,M))
else:
  print(-1)

Solution (Python):
from fractions import gcd

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

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

gcd=gcd(M,N)

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

print((M*N)//gcd)

Solution (Python):
from fractions import gcd

def exist_good_str(N,M,S,T,L):
  X = {}
  for idx, s in enumerate(S):
    if idx != 0: idx = L//N*idx
    if idx in X and X[idx] != s: return False
    else: X[idx] = s
    
  for idx, t in enumerate(T):
    if idx != 0: idx = L//M*idx 
    if idx in X and X[idx] != t: return False
    else: X[idx] = t
  return True
      
N,M = map(int,input().split())
S,T = input(), input()

L = int((N * M / gcd(N, M)))
if exist_good_str(N,M,S,T,L) is True: print(L)
else: print(-1)

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

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

def main():
    N,M = map(int,input().split())
    S = input().strip()
    T = input().strip()
    L = lcm(N,M)
    for i in range(fractions.gcd(N,M)):
        if S[i*L//M] != T[i*L//N]:
            print("-1")
            return
    print(L)

if __name__ == '__main__':
    main()