Problem:
 Score : 300 points    Problem Statement You are given a string S of length N and another string T of length M .
These strings consist of lowercase English letters.  A string X is called a good string when the following conditions are all met:   Let L be the length of X . L is divisible by both N and M .  Concatenating the 1 -st, (\frac{L}{N}+1) -th, (2 \times \frac{L}{N}+1) -th, ... , ((N-1)\times\frac{L}{N}+1) -th characters of X , without changing the order, results in S .  Concatenating the 1 -st, (\frac{L}{M}+1) -th, (2 \times \frac{L}{M}+1) -th, ... , ((M-1)\times\frac{L}{M}+1) -th characters of X , without changing the order, results in T .   Determine if there exists a good string. If it exists, find the length of the shortest such string.      Constraints  1 \leq N,M \leq 10^5  S and T consist of lowercase English letters.  |S|=N  |T|=M         Input Input is given from Standard Input in the following format:  N  M  S  T       Output If a good string does not exist, print -1 ; if it exists, print the length of the shortest such string.        Sample Input 1 3 2
acp
ae      Sample Output 1 6  For example, the string accept is a good string.
There is no good string shorter than this, so the answer is 6 .       Sample Input 2 6 3
abcdef
abc      Sample Output 2 -1       Sample Input 3 15 9
dnsusrayukuaiia
dujrunuma      Sample Output 3 45

Solution (Python):
import math
import numpy as np

N,M=map(int,input().split())
gcd=math.gcd(N,M)
lcm=N*M//gcd

S=input()
T=input()
i=1

L=np.array([lcm*i for i in range(1,max(N,M)) if lcm*i<=N*M])
S_list=L//M
T_list=L//N

if S[0]!=T[0]:
  print(-1)
else:
  for i in range(len(S_list)-1):
    if S[S_list[i]]!=T[T_list[i]]:
      print(-1)
      break
  else:
    print(lcm)

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

    def lcm(x, y):
        return x * y // gcd(x, y)
    N, M = LI()
    S = SI()
    T = SI()
    L = lcm(N,M)
    for i in range(N):
        if i*M%N!=0:
            continue
        cur = i*M//N
        
        if S[i]!=T[cur]:
            L = -1
            break
    print(L)
    return

def examB():
    class combination():
        
        def __init__(self, n, mod):
            self.n = n
            self.mod = mod
            self.fac = [1] * (n + 1)
            self.inv = [1] * (n + 1)
            for j in range(1, n + 1):
                self.fac[j] = self.fac[j - 1] * j % mod

            self.inv[n] = pow(self.fac[n], mod - 2, mod)
            for j in range(n - 1, -1, -1):
                self.inv[j] = self.inv[j + 1] * (j + 1) % mod

        def comb(self, n, r):
            if r > n or n < 0 or r < 0:
                return 0
            return self.fac[n] * self.inv[n - r] * self.inv[r] % self.mod
    N = I()
    A = LI()
    C = combination(N,mod)
    ans = 0
    cnt = 0
    for i in range(N):
        cnt += C.fac[N]*pow(i+1,mod-2,mod)
        cnt %= mod
        
    
    ans += cnt*A[0]
    for i in range(1,N):
        cnt = cnt + C.fac[N]*pow(i+1,mod-2,mod) - C.fac[N]*pow(N-i+1,mod-2,mod)
        cnt += mod
        cnt %= mod
        a = A[i]
        ans += cnt*a
        ans %= mod
        
    print(ans)
    return

def examC():
    ans = 0
    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examA()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Solution (Python):
import fractions

n,m=list(map(int,input().split()))
s=input()
t=input()
l=n*m//fractions.gcd(n,m)

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

pos=0
while pos<l:
    if s[pos//m]!=t[pos//n]:
        print(-1)
        exit(0)

    pos+=p

print(l)

Solution (Python):



from math import gcd


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


def solve(n,m,s,t):
  L = lcm(n,m)
  G = gcd(n,m)
  s_interval = L//n
  t_interval = L//m
  for i in range(G):
    if s[i*n//G] != t[i*m//G]:
      return -1
  return L
  

def main():
  N,M = map(int,input().split())
  s = input()
  t = input()
  print(solve(N,M,s,t))
  return

if __name__ == '__main__':
  main()

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

    G = math.gcd(N, M)
    L = (N * M) // G

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

    print(L)

if __name__ == "__main__":
    main5()

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

    L = (N * M) // math.gcd(N, M)

    pair = dict()

    for i in range(1, N + 1):
        idx = (i - 1) * (L // N) + 1
        pair[idx] = S[i - 1]

    for i in range(1, M + 1):
        idx = (i - 1) * (L // M) + 1

        if idx in pair.keys():
            if pair[idx] != T[i - 1]:
                print(-1)
                exit()

    print(L)

if __name__ == "__main__":
    main4()

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

Solution (Python):
import math
N,M = map(int,input().split())
S = input()
T = input()
G = math.gcd(N,M)
a,b = N//G,M//G
S = S[0::a]
T = T[0::b]
if S == T:
    print(a*b*G)
else:
    print(-1)

Solution (Python):
import math

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


def lcm(x, y):
    return (x * y) // math.gcd(x, y)
l = (lcm(n, m))

sdict = {}
s_num = []
for i, moji in enumerate(list(s)):
    num = i * l // n + 1
    sdict[num - 1] = moji
    s_num.append(num - 1)

tdct = {}
t_num = []
for i, moji in enumerate(list(t)):
    num = i * l // m + 1
    tdct[num - 1] = moji
    t_num.append(num - 1)

stlst = list(set(s_num) & set(t_num))

for i in stlst:
    if sdict[i] != tdct[i]:
        print(-1)
        exit()
print(l)

Solution (Python):
import math
n,m = map(int,input().split())
s = input()
t = input()
lcm = n*m//math.gcd(n,m)
ans = []
s_ind = lcm//n
t_ind = lcm//m
check_ind = s_ind*t_ind//math.gcd(s_ind,t_ind)
for i in range(0,lcm,check_ind):
    if s[i//s_ind] != t[i//t_ind]:
        print(-1)
        exit()
print(lcm)

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


N, M = map(int, input().split())
S = input()
T = input()
x = gcd(N, M)
n = N // x
m = M // x

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

Solution (Python):

from math import gcd

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

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)

G=gcd(n,m)
a,b = n//G,m//G
s=s[0::a]
t=t[0::b]
if s==t: print(a*b*G)
else: print(-1)

Solution (Python):
from collections import defaultdict
from collections import deque
from collections import Counter
import itertools
import math

def readInt():
  return int(input())
def readInts():
  return list(map(int, input().split()))
def readChar():
  return input()
def readChars():
  return input().split()

n,m = readInts()
s = readChar()
t = readChar()

d = defaultdict(str)

l = n*m//math.gcd(n,m)
j = 0
for i in range(1,(n-1)*(l//n)+1+1,l//n):
  d[i]=s[j]
  j+=1
j = 0
for i in range(1,(m-1)*(l//m)+1+1,l//m):
  if not (d[i]=="" or d[i]==t[j]):
    
    print(-1)
    exit()
  j+=1
print(l)

Solution (Python):
import sys

readline = sys.stdin.readline
MOD = 10 ** 9 + 7
INF = float('INF')
sys.setrecursionlimit(10 ** 5)


def main():
    from math import gcd

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

    d = dict()
    l = (n * m) // gcd(n, m)
    ls = l // n
    lt = l // m

    for i in range(n):
        d[i*ls] = s[i]

    for i in range(m):
        if d.get(i*lt):
            if d[i*lt] != t[i]:
                return print(-1)

    print(l)

if __name__ == '__main__':
    main()

Solution (Python):
from math import gcd

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

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

Solution (Python):
import math

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

S=input()
T=input()

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

l=lcm(N,M)

if S[0] != T[0]:
    print(-1)
else:
    a=l//N
    b=l//M
    m=lcm(a,b)
    answer=0
    for n in range(m, l, m):
        c=n//a
        d=n//b
        if S[c]==T[d]:
            continue
        else:
            answer=1
            break
    if answer==0:
        print(l)
    else:
        print(-1)

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

from math import*
ans=N*M//gcd(N,M)

i=0
j=0
count_i=0
count_j=0
while i<N and j<M:
    if count_i==count_j:
        if S[i]!=T[j]:
            ans=-1
    if count_i>count_j:
        count_j+=ans//M
        j+=1
    elif count_j>count_i:
        count_i+=ans//N
        i+=1
    else:
        count_i+=ans//N
        count_j+=ans//M
        i+=1
        j+=1

print(ans)

Solution (Python):
import sys
N, M = list(map(int, input().split()))
S = input()
T = input()
if S[0] != T[0]:
    print(-1)
    sys.exit()
if N > M:
    N, M = M, N
    S, T = T, S


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


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

Solution (Python):
import sys
input = sys.stdin.readline
enum = enumerate
INF = 1001001001

def linput(ty=int, cvt=list):
	return cvt(map(ty,input().rstrip().split()))

def vinput(rep=1, ty=int, cvt=list):
	return cvt(ty(input().rstrip()) for _ in "*"*rep)

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

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

def main():
	N,M = linput()
	S,T = vinput(2,str)
	
	g = gcd(N,M)
	l = lcm(N,M)
	
	res = 0
	if S[::N//g]==T[::M//g]:
		
		
		res = l
	else:
		res = -1
	
	
	
	print(res)


if __name__ == "__main__":
	main()

Solution (Python):
import re
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
import functools
def v(): return input()
def k(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def X(): return list(input())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
cnt = 0
ans = 0
inf = float("inf")

n,m = I()
s = v()
t = v()
l = lcm(n,m)
g = math.gcd(n,m)

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

print(l)

Solution (Python):






import math





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





g = math.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 resolve():
    '''
    code here
    '''
    import math
    N, M = [int(item) for item in input().split()]
    S = input()
    T = input()

    res = N * M // math.gcd(N,M)

    cycle_s = res // N
    cycle_t = res // M
    cycle_overlap = cycle_s * cycle_t // math.gcd(cycle_s, cycle_t)

    for i in range(res//cycle_overlap):        
        if T[i*cycle_overlap//cycle_t] == S[i*cycle_overlap//cycle_s]:
            pass
        else:
            res = -1
            break

    print(res)

if __name__ == "__main__":
    resolve()

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)

isGood=True
cycle_s=L//n
cycle_t=L//m
cycle_lcm=lcm(cycle_s,cycle_t)
for i in range((L//cycle_lcm)):
    if s[cycle_lcm*i//cycle_s]!=t[cycle_lcm*i//cycle_t]:
        isGood=False
        break

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

Solution (Python):
import math

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

N, M = map(int, input().split())
S = input()
T = input()
L = lcm(N , M)
x = {}
for i in range(N):
    idx = i * (L // N)
    x[idx] = S[i]
for i in range(M):
    idx = i * (L // M)
    if idx in x and x[idx] != T[i]:
        print(-1)
        exit()
print(L)

Solution (Python):
import math
n,m=map(int,input().split())
s=input()
t=input()
g = n * m // math.gcd(n, m)

'''if n<m:
    s,t=t,s
    snum,tnum=tnum,snum'''

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

Solution (Python):

import sys
from collections import deque, defaultdict
from math import sqrt, factorial, gcd





def solve():
    n, m = [int(x) for x in input().split()]
    s = input()
    t = input()
    g = gcd(n, m)
    ans = n * m // g
    a, b = n // g, m // g
    x, y = 0, 0
    for i in range(g):
        if s[x] != t[y]:
            print(-1)
            return
        x += a
        y += b
    print(ans)
    
t = 1

for case in range(1,t+1):
    ans = solve()


"""

2 2 2 2 2

"""

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

cnt = math.gcd(N, M)
ans = N * M // cnt
a, b = 0, 0
flag = False
for i in range(cnt):
  if S[a] != T[b]:
    flag = True
    break
  a += N//cnt
  b += M//cnt
  
if flag:
  ans = -1
print(ans)

Solution (Python):
import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

n,m=map(int,input().split())
s=input()
t=input()
g=math.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):
from math import *
a,b=map(int,input().split())
s=input()
t=input()
g=gcd(a,b)
for i in range(g):
    if s[a//g*i]!=t[b//g*i]:
        print(-1)
        exit()
print(a*b//g)

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

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

L = N*M//math.gcd(N,M)

sn = L//M
tm = L//N

for i in range(N//sn):
    if S[i*sn] == T[i*tm]:
        continue
    else:
        print(-1)
        exit()
print(L)

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


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_lcm = lcm(len(S), len(T))
gcd_nm = gcd(N, M)

s_step = N // gcd_nm
t_step = M // gcd_nm

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

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

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

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

def cond(candidate):
    count = gcd(n, m)
    n_step = n // count
    m_step = m // count

    for i in range(count):
        if s[n_step * i] != t[m_step * i]:
            return False
    return True

candidate = lcm(n, m)

if cond(candidate):
    print(candidate)
else:
    print(-1)

Solution (Python):
from math import gcd
n, m, S, T = open(0).read().split()
n, m = int(n), int(m)
l = n*m // gcd(n, m)

d = {}
t = l//n
for i in range(n):
    d[i*t] = S[i]
t = l//m
for i in range(m):
    if i*t not in d or d[i*t] == T[i]:
        d[i*t] = T[i]
    else:
        print(-1)
        break
else:
    print(l)

Solution (Python):
from math import gcd

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

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

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

print(L)

Solution (Python):
from math import gcd


def lcm(X, Y):  
    return (X * Y) // gcd(X, Y)

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

l = lcm(n, m)
ln, lm = l // n, l // m
if all(s[i // ln] == t[i // lm] for i in range(0, l, lcm(ln, lm))):
    print(l)
else:
    print(-1)

Solution (Python):
from math import gcd


def lcm(X, Y):  
    return (X * Y) // gcd(X, Y)

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

l = lcm(n,m)
ln, lm = l // n, l // m
for i in range(0, l, lcm(ln, lm)):
    if s[i // ln] != t[i // lm]:
        print(-1)
        break
else:
    print(l)

Solution (Python):
import sys, os, math, bisect, itertools, collections, heapq, queue

from decimal import Decimal
from collections import defaultdict, deque

sys.setrecursionlimit(10000000)

ii = lambda: int(sys.stdin.buffer.readline().rstrip())
il = lambda: list(map(int, sys.stdin.buffer.readline().split()))
fl = lambda: list(map(float, sys.stdin.buffer.readline().split()))
iln = lambda n: [int(sys.stdin.buffer.readline().rstrip()) for _ in range(n)]

iss = lambda: sys.stdin.buffer.readline().decode().rstrip()
sl = lambda: list(map(str, sys.stdin.buffer.readline().decode().split()))
isn = lambda n: [sys.stdin.buffer.readline().decode().rstrip() for _ in range(n)]

lcm = lambda x, y: (x * y) // math.gcd(x, y)

MOD = 10 ** 9 + 7
MAX = float('inf')


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

    N, M = il()
    S = iss()
    T = iss()
    G = math.gcd(N, M)

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


if __name__ == '__main__':
    main()

Solution (Python):
import math

import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    n,m = map(int,ipt().split())
    s = input()
    t = input()
    g = math.gcd(n,m)
    l = n*m//g
    sg = n//g
    tg = m//g
    for i in range(g):
        if s[sg*i] != t[tg*i]:
            print(-1)
            exit()

    print(l)

    return

if __name__ == '__main__':
    main()

Solution (Python):
import sys
import math
read = sys.stdin.read
readline = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 8)
INF = float('inf')
MOD = 10 ** 9 + 7

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

    G = math.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)


if __name__ == '__main__':
    main()

Solution (Python):
from math import gcd

def lcm(a,b):
    return (a*b)//gcd(a,b)
N,M=map(int, input().split())
S=input()
T=input()

L=lcm(N,M)

i=0
j=0
while 0<=i<N and 0<=j<M:
    nowi=i*(L//N)
    nowj=j*(L//M)
    
    if nowj==nowi:
        if S[i]!=T[j]:

            print(-1)
            exit()

    if nowi>nowj:
        j+=1
    elif nowi<nowj:
        i+=1
    else:
        i+=1
        j+=1
print(L)

Solution (Python):
from math import gcd
from collections import defaultdict

N, M = map(int, input().split())
S = input()
T = input()
g = N//gcd(N, M)*M
ans = defaultdict(bool)
for i in range(N):
    ans[i*g//N] = S[i]
ok = True
for i in range(M):
    idx = i*g//M
    if ans[idx] and ans[idx] != T[i]:
        ok = False
        break
if ok:
    print(g)
else:
    print(-1)

Solution (Python):
import bisect,copy,heapq,string
from collections import *
from math import *
from itertools import *
import sys
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n, m = MAP()
s = input()
t = input()
k = gcd(n,m)
l = n*m//k

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

Solution (Python):
from math import gcd
from collections import defaultdict

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

ans = n*m // gcd(n,m)
d = defaultdict(lambda : '?')

for i,si in enumerate(s):
    d[i * ans//n] = si

for j,tj in enumerate(t):
    if(not d[j * ans//m] in ['?', tj]):
        print(-1)
        exit()

print(ans)

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")

from collections import defaultdict
import math
n,m = map(int, input().split())
s = input()
t = input()
g = math.gcd(n,m)
d = defaultdict(list)
for i in range(n):
    ind = i*(m//g)
    d[ind].append(s[i])
for i in range(m):
    ind = i*(n//g)
    d[ind].append(t[i])
for k,v in d.items():
    if v and not all(item==v[0] for item in v):
        ans = -1
        break
else:
    ans = n*m//g
print(ans)

Solution (Python):
import math
def lcm(x, y):
    return (x * y) // math.gcd(x, y)
N,M = map(int,input().split())
S = input()
T = input()

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

Solution (Python):
def gcd(a,b):
    if(a%b!=0):
        return gcd(b,a%b)
    else:
        return b
def lcm(a,b):
    return (a*b//(gcd(a,b)))
def main3():
    n,m=map(int, input().split())
    s=input()
    t=input()
    if(n>m):
        s1 = t
        t1 = s
    else:
        s1 = s
        t1 = t
    l = (lcm(n,m))
    l_n = l//n
    l_m = l//m
    i = 0
    ind_min = []
    ind_max = []
    while(i<min(n,m)):
        ind_min.append(i*max(l_n,l_m)+1)
        i+=1
    i = 0
    while(i<max(n,m)):
        ind_max.append(i*min(l_n,l_m)+1)
        i+=1

    ind_max_d = {k:i for i,k in enumerate(ind_max)}

    for i in range(len(ind_min)):
        if(ind_min[i] in ind_max_d):
            if(s1[i] != t1[ind_max_d[ind_min[i]]]):
                print(-1)
                exit()
    print(l)



if __name__ == '__main__':
    main3()

Solution (Python):
N, M=map(int, input().split())
s=input()
t=input()
from math import gcd

g=gcd(N,M)

if g==1:
  ans=(N*M)//g
else:
  n=N//g
  m=M//g
  import numpy as np
  pn=np.arange(m, M, m)
  qm=np.arange(n, N, n)
  ans=(N*M)//g
  for i in range(len(pn)):
    if s[qm[i]]!=t[pn[i]]:
      ans=-1
      break
if s[0]!=t[0]:
  ans=-1
print(ans)

Solution (Python):
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7
 
N,M = I()
S = list(s())
T = list(s())
n = lcm(N,M)
l = (N-1)//(n//M)
for i in range(l+1):
    if S[i*(n//M)] != T[i*(n//N)]:
        print(-1)
        exit()
print(n)

Solution (Python):
from math import gcd
N, M = map(int, input().split())
S = input()
T = input()
G = gcd(N, M)
 
for i in range(G):
    if S[i * N // G] != T[i * M // G]:
        print(-1)
        exit()
 
l = N * M // G
print(l)

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

Solution (Python):
from math import gcd
import numpy
N, M = map(int, input().split())
S = input()
T = input()
def func(m, n):
    return (m * n) // gcd(m, n)
ans = func(N, M)
var1 = ans//N
var2 = ans//M
for i in range(1, ans+1, var1*var2):
    varS = (i - 1) // var1
    varT = (i - 1) // var2
    if S[varS] != T[varT]:
        ans=-1
print(ans)

Solution (Python):
from math 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)
    exit()
print(N//G * M//G * G)

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


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



l = N * M // G
print(l)

Solution (Python):
from math import gcd

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

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

lc = lcm(N, M)

ss = lc//N
tt = lc//M

for i in range(1, lc+1, ss*tt):
    s_tmp = (i - 1) // ss
    t_tmp = (i - 1) // tt

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

print(lc)

Solution (Python):
import math


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


N, M = map(int, input().split())
S = input()
T = input()
L = lcm(N, M)
G = math.gcd(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 math 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)
    exit()
print(N//G * M//G * G)

Solution (Python):
from math import gcd

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

g=gcd(n,m)

ng=n//g
mg=m//g

for i in range(0,g):
    if s[ng*i]!=t[mg*i]:
        print(-1)
        exit()
print(ng*mg*g)

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

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

lcm = N * M // math.gcd(N, M)

tekito =[]
for i in range(1,N):
  tekito.append(i*(lcm//N)+1)
tekitu =[]
for i in range(1,M):
  tekitu.append(i*(lcm//M)+1)

gattai = set(tekito) & set(tekitu) 
for k in gattai:
  i1 = (k-1) // (lcm//N)
  i2 = (k-1) // (lcm//M)
  if S[i1] != T[i2]:
    print(-1)
    exit()
print(lcm)

Solution (Python):




import sys
sys.setrecursionlimit(1 << 25)
read = sys.stdin.readline
ra = range
enu = enumerate


def mina(*argv, sub=1): return list(map(lambda x: x - sub, argv))



def read_ints(): return list(map(int, read().split()))


from math import gcd


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


N, M = read_ints()
S = read()[:-1]
T = read()[:-1]

L = lcm(N, M)

s_step = N // gcd(N, M)
t_step = M // gcd(N, M)
print(L if S[::s_step] == T[::t_step] else -1)

Solution (Python):
import math

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

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

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

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

Solution (Python):
import sys
import math
import itertools
import bisect
from copy import copy
from collections import deque,Counter
from decimal import Decimal
def s(): return input()
def i(): return int(input())
def S(): return input().split()
def I(): return map(int,input().split())
def L(): return list(input().split())
def l(): return list(map(int,input().split()))
def lcm(a,b): return a*b//math.gcd(a,b)
sys.setrecursionlimit(10 ** 9)
mod = 10**9+7

N,M = I()
S = list(s())
T = list(s())
n = lcm(N,M)
l = (N-1)//(n//M)
for i in range(l+1):
    if S[i*(n//M)] != T[i*(n//N)]:
        print(-1)
        exit()
print(n)

Solution (Python):
import sys
INF = 1 << 60
MOD = 10**9 + 7 
sys.setrecursionlimit(2147483647)
input = lambda:sys.stdin.readline().rstrip()
from math import gcd
def resolve():
    fixed = {}
    n, m = map(int, input().split())
    S = input()
    T = input()
    l = n // gcd(n, m) * m
    for i in range(n):
        fixed[i * l // n] = S[i]
    for j in range(m):
        if not j * l // m in fixed:
            continue
        if fixed[j * l // m] != T[j]:
            print(-1)
            return
    print(l)
resolve()

Solution (Python):
import sys
sys.setrecursionlimit(10000000)
MOD = 10 ** 9 + 7
INF = 10 ** 15

from math import gcd
def main():
    N,M = map(int,input().split())
    S = input()
    T = input()

    lcm = N*M//gcd(N,M)
    
    x = lcm//N
    y = lcm//M
    
    ans = lcm
    for i in range(N):
        j = x * i
        if j%y == 0:
            if S[i] != T[j//y]:
                ans = -1
                break
    
    for j in range(M):
        i = y * j
        if i%x == 0:
            if S[i//x] != T[j]:
                ans = -1
                break
    print(ans)  
if __name__ == '__main__':
    main()

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

def gcd(x, y):
    while y:
        x, y = y, x % y
    return x

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

g = gcd(n, m)
bl = True
for k in range(g):
    i, j = k * n // g, k * m // g
    if s[i] != t[j]: 
        bl = False

print(lcm(n, m)) if bl else print('-1')

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(str, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7


N, M = MAP()

S = input()
T = input()

L = N*M//gcd(N, M)
G = gcd(N, M)

for i in range(G):
	if S[N//G*i] != T[M//G*i]:
		print(-1)
		break
else:
	print(L)