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
def lcm(a, b):
    return (a*b)//gcd(a, b)
N,M = map(int, input().split())
S = input()
T = input()
L = gcd(N,M)

if all([S[i*N//L] == T[i*M//L] for i in range(L)]):
    print(lcm(N,M))
else:
    print('-1')

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


def lcm(a, b):
	return a * b // gcd (a, b)
n,m = map(int,input().split())
s = input()
t = input()
mx = max(n,m)
mn = min(n,m)
if mx / mn % 1 == 0:
    c = mx//mn
    if mn == len(s):
        if s == t[::c]:
            print(t[::c])
            print(mx)
        else:
            print(-1)
    else:
        if t == s[::c]:
            print(s[::c])
            print(mx)
        else:
            print(-1)
else:
    num = lcm(n,m)
    mmx = num // mx
    mmn = num // mn
    ber = lcm(mmx,mmn)
    if mn == len(s):
        if s[::ber//mmn] == t[::ber//mmx]:
            print(num)
        else:
            print(-1)
    else:
        if s[::ber//mmx] == t[::ber//mmn]:
            print(num)
        else:
            print(-1)

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

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


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

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


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

x = {}
for i,c in enumerate(s):
    
    x[lcm//n*i] = c

for i,c in enumerate(t):
    
    pos, char = lcm//m*i, c
    if pos in x and x[pos] != char:
        print(-1)
        exit()

print(lcm)

Solution (Python):
import sys
import itertools

import time
import math
from heapq import heappop, heappush
from collections import defaultdict
from collections import Counter
from collections import deque
from itertools import permutations
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines


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

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

si = lcm // M
ti = lcm // N

i = 0
j = 0
ok = True
while i < N and j < M:
    if S[i] != T[j]:
        ok = False
        break
    i += si
    j += ti
if ok:
    print(lcm)
else:
    print(-1)

Solution (Python):


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

def gcd(x, y):
    if x < y:
        x, y = y, x

    if y == 0:
        return x

    else:
        return gcd(y, x % y)

nm = gcd(N, M)

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

else:
    sp = N // nm
    tp = M // nm

    si = 0
    ti = 0

    ans = True

    while (si < N and ti < M):
        if S[si] == T[ti]:
            si += sp
            ti += tp
        else:
            ans = False
            break

    if ans:
        print(N * M // nm)
    else:
        print(-1)

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

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

Solution (Python):
from collections import defaultdict
import math
n,m = map(int, input().split())
s = input()
t = input()

ans = int((n*m)/math.gcd(n,m))
d = defaultdict(int)
if n > m:
  for i in range(n):
    if i == 0:
      d[1] = s[i]
    else:
      d[i*int(ans/n)+1] = s[i]
  ng = 0
  for i in range(m):
    if i == 0:
      if d[1] != t[i]:
        ng += 1
    else:
      if d[i*int(ans/m)+1] != 0 and d[i*int(ans/m)+1] != t[i]:
        ng += 1
else:
  for i in range(m):
    if i == 0:
      d[1] = t[i]
    else:
      d[i*int(ans/m)+1] = t[i]
  ng = 0
  for i in range(n):
    if i == 0:
      if d[1] != s[i]:
        ng += 1
    else:
      if d[i*int(ans/n)+1] != 0 and d[i*int(ans/n)+1] != s[i]:
        ng += 1
if ng > 0:
  print (-1)
else:
  print (ans)

Solution (Python):
import math

class common_function():
    """
        1. よく使いそうで予め用意しておいた変数をまとめた
        2. よく使いそうな関数群をまとめた
    """
    def lcm(self, x:int, y:int):
        """
            最小公倍数を返すメソッド
            math をインポートする
        """
        return (x * y) // math.gcd(x, y)
        

def main():
    common = common_function()
    N, M = map(int, input().split())
    S = input()
    T = input()
    lengthX = common.lcm(N, M)
    XdivS = lengthX//N
    XdivT = lengthX//M
    X = []
    for i in range(N):
        j = XdivS*i
        X.append((j, S[i]))
    X.sort(key=lambda x: x[0], reverse=True)
    
    k, x = X.pop()
    for i in range(M):
        j = XdivT*i
        for a in range(lengthX):
            if len(X) == 0:
                break
            if k < j:
                k, x = X.pop()
            else:
                break
        if k == j:
            if x != T[i]:
                print(-1)
                return
    print(lengthX)

if __name__ == "__main__":
    main()

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

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

"""
最小公倍数の長さで収まらない場合は、何をやってもダメ
"""
for i in range(g):
    if not s[i*n//g] == t[i*m//g]:
        print(-1)
        exit(0)
print(ans)

Solution (Python):
n,m=map(int,input().split())
s=input() ;a=len(s)
t=input() ;b=len(t)
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(len(s),len(t))

d={}
now=0
for i in range(0,L,L//a):
    d[i]=s[now]
    now+=1
now=0
for j in range(0,L,L//b):
    if d.get(j, t[now])!=t[now]:
        print(-1);exit()
    now+=1
print(L)

Solution (Python):
n,m=map(int,input().split())
s=input() ;a=len(s)
t=input() ;b=len(t)
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(len(s),len(t))

d={}
now=0
for i in range(0,L,L//a):
    d[i]=s[now]
    now+=1
now=0
for j in range(0,L,L//b):
    if d.get(j, t[now])!=t[now]:
        print(-1);exit()
    now+=1
print(L)

Solution (Python):
import sys


def get_lcm(a, b):
	import math
	return (a * b) // math.gcd(a, b)


def is_match(X, L):
  global M
  global T

  i = 0
  m = L//M * i

  while m + 1 < L:
    if m+1 in X.keys():
      if X[m+1] != T[i]:
        return False

    i += 1
    m = L//M * i

  return True


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

if S[0] != T[0]:
  print(-1)
else:
  lcm = get_lcm(N, M)

  for i in range(1, 100):
    L = lcm * i
    X = dict()

    j = 0
    n = L//N * j

    while n + 1 < L:
      X[n+1] = S[j]

      j += 1
      n = L//N * j

    if is_match(X, L):
      print(L)
      exit()

  print(-1)

Solution (Python):
import sys, math
from functools import lru_cache
from collections import defaultdict
from decimal import Decimal
sys.setrecursionlimit(10**9)
MOD = 10**9+7

def input():
    return sys.stdin.readline()[:-1]

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

def ii():
    return int(input())

def i2(n):
    tmp = [list(mi()) for i in range(n)]
    return [list(i) for i in zip(*tmp)]

def main():
    N, M = mi()
    S, T = [list(input()), list(input())]

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

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

    print(l)


if __name__ == '__main__':
    main()

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

Solution (Python):
from math import gcd
n,m=map(int,input().split())
s=input()
t=input()
res=n*m//gcd(n,m)
a=m//gcd(n,m)
b=n//gcd(n,m)
if n>=m:
  for i in range(m):
    if (i*b)%a==0:
      if s[(i*b)//a]!=t[i]:
        print(-1)
        exit()
else:
  for i in range(n):
    if (i*a)%b==0:
      if s[i]!=t[(i*a)//b]:
        print(-1)
        exit()
print(res)

Solution (Python):

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

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

dist_N = L//N
dist_M = L//M


for i in range(GCD):
    
    s = dist_M * i
    t = dist_N * i
    if S[s] != T[t]:
        ans = -1
        break
else:
    ans = L
print(ans)

Solution (Python):
from math import gcd
n,m = map(int,input().split())
z = n * m // gcd(n,m)
s = input()
t = input()
n = z // n
m = z // m
x = 0
y = 0
i = 0
j = 0
while x < z and y < z:
    if x > y:
        y += m
        j += 1
    elif x < y:
        x += n
        i += 1
    else:
        if s[i] != t[j]:
            print(-1)
            exit(0)
        x += n
        y += m
        i += 1
        j += 1
print(z)

Solution (Python):
import sys
from sys import exit
from collections import deque
from bisect import bisect_left, bisect_right, insort_left, insort_right 
from heapq import heapify, heappop, heappush
from itertools import product, permutations, combinations, combinations_with_replacement
from math import *

sys.setrecursionlimit(10**6)
INF = 10**20
eps = 1.0e-20
MOD = 10**9+7

def lcm(x,y):
    return x*y//gcd(x,y)
def lgcd(l):
    return reduce(gcd,l)
def llcm(l):
    return reduce(lcm,l)
def mint():
    return map(int,input().split())
def lint():
    return list(map(int,input().split()))
def ilint():
    return int(input()), list(map(int,input().split()))
def judge(x, l=['Yes', 'No']):
    print(l[0] if x else l[1])
def lprint(l, sep='\n'):
    for x in l:
        print(x, end=sep)
def ston(c, c0='a'):
    return ord(c)-ord(c0)
def ntos(x, c0='a'):
    return chr(x+ord(c0))
class counter(dict):
    def __init__(self, *args):
        super().__init__(args)
    def add(self,x):
        self.setdefault(x,0)
        self[x] += 1

N,M = mint()
S,T = input(),input()
l,g = lcm(N,M),gcd(N,M)
ans = True
for i in range(g):
    if S[i*l//M]!=T[i*l//N]:
        ans = False
        break
print(l if ans else -1)

Solution (Python):
from math import gcd
from sys import exit
n, m = map(int, input().split())
s = input()
t = input()
x = gcd(n, m)
y = n * m // x
a = n // x
b = m // x
for i in range(x):
    if s[i * a] != t[i * b]:
        print(-1)
        exit()
print(y)

Solution (Python):

import math


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


def main():
    n, m = map(int, input().split())
    s = input()
    t = input()
    ans = lcm(n, m)
    ln = ans // n
    lm = ans // m
    l = lcm(ln, lm)
    i = 0
    while i * l // ln < n and i * l // lm < m:
        if s[i * l // ln] != t[i * l // lm]:
            ans = -1
            break
        i += 1

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import math
N,M = map(int,input().split())
S = input()
T = input()
L = N * M // math.gcd(N,M)
NN = L // N
MM = L // M

for i in range(10**6):
    if MM*i > len(S)-1 or NN*i > len(T)-1:
        break
    if S[i*MM] != T[i*NN]:
        print(-1)
        exit()
print(L)

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

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

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




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


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


l = lcm(N, M)

s = l // N
t = l // M

S_set = set([s * i for i in range(N)])
T_set = set([t * i for i in range(M)])

_set = S_set & T_set


for i in _set:
    if S[i // s] != T[i // t]:
        print(-1)
        exit()
print(l)

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

Solution (Python):
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():
    from functools import reduce
    def lcm_base(n1,n2):
        return (n1*n2)//math.gcd(n1,n2)
    def lcm(*numbers):
        return reduce(lcm_base, numbers)
    n,m = LI()
    s = S()
    t = S()
    l1 = lcm(n,m)
    s_unit = l1//n
    t_unit = l1//m
    l2 = lcm(s_unit, t_unit)
    time = (l1-1)//l2+1
    itr = [l2*i for i in range(time)]
    ans = l1

    for i in itr:
        si = i//s_unit
        ti = i//t_unit
        if s[si] != t[ti]:
            ans = -1

    print(ans)

main()

Solution (Python):
import bisect,collections,copy,itertools,math,string
import sys
def I(): return int(sys.stdin.readline().rstrip())
def LI(): return list(map(int,sys.stdin.readline().rstrip().split()))
def S(): return sys.stdin.readline().rstrip()
def LS(): return list(sys.stdin.readline().rstrip().split())
def main():
    from functools import reduce
    def lcm_base(n1,n2):
        return (n1*n2)//math.gcd(n1,n2)
    def lcm(*numbers):
        return reduce(lcm_base, numbers)
    n,m = LI()
    s = S()
    t = S()
    l1 = lcm(n,m)
    s_unit = l1//n
    t_unit = l1//m
    l2 = lcm(s_unit, t_unit)
    time = (l1-1)//l2+1
    itr = [l2*i for i in range(time)]
    ans = l1

    for i in itr:
        si = i//s_unit
        ti = i//t_unit
        if s[si] != t[ti]:
            ans = -1

    print(ans)

main()

Solution (Python):
import sys
import math


inint = lambda: int(sys.stdin.readline())
inintm = lambda: map(int, sys.stdin.readline().split())
inintl = lambda: list(inintm())
instrm = lambda: map(str, sys.stdin.readline().split())
instrl = lambda: list(instrm())

n, m = inintm()
s = input()
t = input()

c = {}

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

lcm_num = lcm(n,m)

for i in range(n):
    c[i*m + 1] = s[i]

for i in range(m):
    if i*n + 1 in c:
        if c[i*n + 1] != t[i]:
            print(-1)
            exit()

print(lcm_num)

Solution (Python):


import sys



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


def input_int():
    return int(input())


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



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



def lcm(x: int, y: int) -> int:
    _gcd = gcd(x, y)
    return (x * y) // _gcd


def main():
    n, m = input_int_list()
    _gcd = gcd(m, n)
    size = lcm(m, n)
    S = input()
    T = input()
    if S[::n // _gcd] == T[::m // _gcd]:
        print(size)
    else:
        print(-1)


if __name__ == "__main__":
    main()

Solution (Python):
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from math import gcd
def main():
    n, m = map(int, input().split())
    s = tuple(input())
    t = tuple(input())

    if n > m:
        l1 = n
        l2 = m
        s1 = s
        s2 = t
    else:
        l1 = m
        l2 = n
        s1 = t
        s2 = s

    if s[0] != t[0]:
        r = -1
    elif n == m:
        if s == t:
            r = n
        else:
            r = -1
    elif n % m == 0 or m % n == 0:
        ld = l1 // l2
        for i1 in range(1, l2):
            if s2[i1] != s1[i1*ld]:
                r = -1
                break
        else:
            r = l1
    else:
        l = (n * m) // gcd(n, m)
        
        ld1 = l // l1
        ld2 = l // l2
        cnt = 1
        r = l
        while cnt < l1:
            cnt2 = cnt * ld1
            if cnt2 % ld2 == 0:
                if s1[cnt] != s2[cnt2 // ld2]:
                    r = -1
                    break
            cnt += 1
    print(r)

if __name__ == '__main__':
    main()

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)
d = {}
s = set()
for i in range(N):
    d[str(i * (L // N))] = S[i]
    s.add(str(i * (L // N)))

for i in range(M):
    key = str(i * (L // M))
    if key in s:
        if d[key] != T[i]:
            print(-1)
            exit()
print(L)

Solution (Python):
import math
import sys
n, m = map(int, input().split())
s = list(input())
t = list(input())
a = (n*m)//math.gcd(n, m)
b0 = [i*(a//n)+1 for i in range(n)]
b1 = [i*(a//m)+1 for i in range(m)]
b2 = set(b0)
b3 = set(b1)

for j, i in enumerate(b0):
    if i in b3:
        if s[j] != t[b1.index(i)]:
            print(-1)
            sys.exit()
            
for j, i in enumerate(b1):
    if i in b2:
        if s[b0.index(i)] != t[j]:
            print(-1)
            sys.exit()
print(a)

Solution (Python):
import math

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

x = math.gcd(n,m)
ans = n*m//x
n = n//x
m = m//x

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

print(ans)

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

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

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

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

Solution (Python):
from math import gcd as g
n,m=map(int,input().split())
s=input()
t=input()
k=(a:=(N:=(l:=n*m//g(n,m))//n))*(b:=(M:=l//m))//g(a,b)
print(-1 if s[0]!=t[0] or (l==n and s!=t*N) or (l==m and t!=s*M) or s[::b]!=t[::a] else l)

Solution (Python):

import sys
import math


def input(): return sys.stdin.readline().strip()
def I(): return int(input())
def LI(): return list(map(int, input().split()))
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def S(): return input()
def LS(): return input().split()


INF = float('inf')


n, m = LI()
s = S()
t = S()

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

Solution (Python):
from math import gcd

n, m = map(int, input().split())
g = gcd(n, m)
s = input()
t = input()
f = True
for i in range(g):
    a = i * n // g
    b = i * m // g
    f &= (s[a] == t[b])

if f:
    print((n * m) // g)
else:
    print(-1)

Solution (Python):
from math import gcd

def lcm(a, b):
    _a = a
    while a % b != 0:
        a += _a
    return a



 
  
   


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


S = input()
T = input()
L = N * M // gcd(N, M)

s_now = 0
t_now = 0
while True:
    if S[s_now] != T[t_now]:
        print(-1)
        break
    s_now += L//M
    t_now += L//N
    if s_now >= N or t_now >= M:
        print(L)
        break

Solution (Python):
import math

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

g = math.gcd(N, M)
lcm = N * M // g
flg = True
N //= g
M //= g
for i in range(g):
    if S[i*N] != T[i*M]:
        flg = False
        break
if flg:
    print(lcm)
else:
    print(-1)

Solution (Python):
import math

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

g = math.gcd(n, m)
n //= g
m //= g

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

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


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


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


l = lcm(len(s), len(t))
x = {}  
for i in range(0, len(s)):
    x[i * (l // len(s))] = s[i]
for i in range(0, len(t)):
    if i * (l // len(t)) not in x:
        continue
    else:
        if x[i * (l // len(t))] != t[i]:
            print(-1)
            exit()
print(l)

Solution (Python):
from math import gcd
n, m = map(int, input().split())
s = list(input())
t = list(input())
g = gcd(n, m)
ans = n*m//g
sp_a, sp_b = m//g, n//g
jud = True
for i in range(ans//sp_a):
    if i*sp_a % sp_b == 0:
        if s[i % n] != t[i*sp_a//sp_b]:
            jud = False

if jud:
    print(ans)
else:
    print(-1)

Solution (Python):
from math import gcd

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

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

cnt = (l // m) * (l // n)
a = [i * l // m for i in range(l // cnt)]
b = [i * l // n for i in range(l // cnt)]

for i in range(l // cnt):
    a1 = a[i]
    b1 = b[i]
    if s[a1] == t[b1]:
        pass
    else:
        print(-1)
        exit()

print(l)

Solution (Python):
import math

n,m = map(int,input().split())
a = input()
b = input()
g = math.gcd(n,m)
l = (n*m)//g
d = {}
for i in range(n):
    d[i*(l//n)] = a[i]
for i in range(m):
    if i*(l//m) in d:
        if d[i*(l//m)] != b[i]:
            print(-1)
            exit()
print(l)

Solution (Python):
import math

n,m = map(int,input().split())
a = input()
b = input()
if a[0] != b[0]:
    print(-1)
    exit()

g = math.gcd(n,m)
if g == 1:
    print(n*m//g)
else:
    l = (n*m)//g
    d = {}
    for i in range(n):
        d[i*(l//n)] = a[i]
    for i in range(m):
        if i*(l//m) in d:
            if d[i*(l//m)] != b[i]:
                print(-1)
                exit()
    print(l)

Solution (Python):
from math import gcd

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

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

P=L//N
Q=L//M

A=range(0,L,P)
B=range(0,L,Q)

F=True
for k in A:
    if k in B:
        F&=S[k//P]==T[k//Q]
if F:
    print(L)
else:
    print(-1)

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()
g = gcd(N,M)
l = lcm(N,M)
for i in range(g):
    if S[l//M*i] != T[l//N*i]:
        print(-1)
        exit()
print(l)

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

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

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

nd = l//n
md = l//m

common = nd*md//gcd(nd,md)
nc = common//nd
mc = common//md

sol = True
for i in range(0, l, common):
    ind = i//common
    if s[ind * nc] != t[ind * mc]:
        sol = False
        break

print(l if sol else -1)

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

print(gn*gm*g)

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

NMgcd = math.gcd(N,M)
Leng  = N*M//NMgcd
Flag  = True
SList = [S[Nk] for Nk in range(0,N) if Nk%(N//NMgcd)==0]

for Mk in range(0,len(SList)):
    if SList[Mk]!=T[Mk*(M//NMgcd)]:
        Flag = False
        break
if Flag:
    print(Leng)
else:
    print(-1)

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

NMG = math.gcd(N,M)
Length = N*M//NMG
Flag   = True
SIndex = [Nk*(M//NMG) for Nk in range(0,N)]
SList  = list(S)

Count = 0
for Mk in range(0,M):
    if Mk%(M//NMG)==0:
        if SList[Count*(N//NMG)]!=T[Mk]:
            Flag = False
            break
        else:
            Count += 1
if Flag:
    print(Length)
else:
    print(-1)

Solution (Python):
import math
N, M = map(int, input().split())
S = list(input())
T = list(input())
lcm = (N * M) // math.gcd(N, M)
ans = lcm
Sp = lcm//N
Tp = lcm//M
lcmlcm = (Sp * Tp) // math.gcd(Sp, Tp)
owari = min(Sp*N, M*Tp)
for i in range(0, owari, lcmlcm):
    if S[i//Sp] != T[i//Tp]:
        ans = -1
        break
print(ans)

Solution (Python):
from math import gcd

N, M = [int(x) for x in input().split()]
S = input()
T = input()

lcm = N * M // gcd(N, M)
count = 1

result = -1


def check(answer_length, line, answer):
    for i in range(0, len(line)):
        idx = i * answer_length // len(line) + 1

        if idx in answer:
            if not answer[idx] == line[i]:
                return False
        else:
            if idx <= answer_length:
                answer[idx] = line[i]
            else:
                return False

    return True


answer = {}
max_str = max((M-1) * (lcm * count) // M + 1,
                  (N-1) * (lcm * count) // N + 1)

if check(lcm * count, S, answer):
    if check(lcm*count, T, answer):
        print(lcm*count)
        exit()

print(result)

Solution (Python):
import math
from functools import reduce


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


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


def solve():
    N, M = [int(x) for x in input().split()]
    S = input()
    T = input()

    L = lcm([N, M])
    ic, jc = 0, 0
    i, j = ic * L // N + 1, jc * L // M + 1
    ans = L
    while ic < N and jc < M:
        
        if i == j:
            if S[ic] != T[jc]:
                ans = '-1'
                break
            ic += 1
            jc += 1
            i = ic * L // N + 1
            j = jc * L // M + 1
        elif i < j:
            ic += 1
            i = ic * L // N + 1
        elif i > j:
            jc += 1
            j = jc * L // M + 1
    print(ans)


if __name__ == '__main__':
    solve()

Solution (Python):
import math
from functools import reduce


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


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


def make_divisors(n):
    lower_divisors, upper_divisors = [], []
    i = 1
    while i * i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n // i)
        i += 1
    return lower_divisors + upper_divisors[::-1]


def commonDivisors(x1, x2):
    cf = []
    for i in range(2, min(x1, x2) + 1):
        if x1 % i == 0 and x2 % i == 0:
            cf.append(i)
    return cf


def solve():
    N, M = [int(x) for x in input().split()]
    S = input()
    T = input()
    
    
    
    
    
    
    
    
    
    
    
    
    L = lcm([N, M])
    ic, jc = 0, 0
    i, j = ic * L // N + 1, jc * L // M + 1
    ans = L
    while ic < N and jc < M:
        
        if i == j:
            if S[ic] != T[jc]:
                ans = '-1'
                break
            ic += 1
            jc += 1
            i = ic * L // N + 1
            j = jc * L // M + 1
        elif i < j:
            ic += 1
            i = ic * L // N + 1
        elif i > j:
            jc += 1
            j = jc * L // M + 1
    print(ans)
    
    
    
    
    
    
    
    
    
    


if __name__ == '__main__':
    solve()

Solution (Python):
import math
N,M = (int(T) for T in input().split())
S = input()
T = input()
Length = N*M//math.gcd(N,M)
Flag   = True
SIndex = [Nk*(Length//N) for Nk in range(0,N)]
SList  = list(S)
    
for Mk in range(0,M):
    if Mk%(Length//N)==0:
        MInd = SIndex.index(Mk*(Length//M))
        if SList[MInd]!=T[Mk]:
            Flag = False
            break
        
if Flag:
    print(Length)
else:
    print(-1)

Solution (Python):
import math

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

GCD = math.gcd(N, M)
a, b = N//GCD, M//GCD
ans = True
for i in range(GCD):
    if S[i*a] != T[i*b]:
        ans = False
        break

if ans:
    print(a*b*GCD)
else:
    print(-1)

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

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

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

A = []
B = []

C = N//math.gcd(N,M)
D = M//math.gcd(N,M)

for i in range (0, math.gcd(N,M)):
	if S[i*C] != T[i*D]:
		print(-1)
		exit()

print(G)

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

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

ds = L // N
dt = L // M
S = S[0::dt]
T = T[0::ds]

if S == T:
    print(L)
else:
    print(-1)

Solution (Python):
import math

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

if n == m:
    if s == t:
        print(n)
    else:
        print(-1)
    exit()

if m == 1:
    n,m = m,n
    s,t = t,s

if n == 1:
    if s[0] == t[0]:
        print(m)
    else:
        print(-1)
    exit()

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

n1 = lcm//n
m1 = lcm//m

lcm2 = n1 * m1 // math.gcd(n1, m1)
stepn = lcm2//n1
stepm = lcm2//m1

for i in range(0,10**5):
    if stepn*i > n-1 or stepm*i > m-1:
        print(lcm)
        break
    if s[stepn*i] != t[stepm*i]:
        print(-1)
        exit()

Solution (Python):
import sys
def input(): return sys.stdin.readline().strip()
def mapint(): return map(int, input().split())
sys.setrecursionlimit(10**9)

N, M = mapint()
S = list(input())
T = list(input())
from math import gcd

leng = N*M//gcd(N, M)
step = (leng//N)*(leng//M)//gcd((leng//N), (leng//M))

for i in range(1, leng+1, step):
    if (i-1)%(leng//N)==0 and(i-1)%(leng//M)==0:
        if S[(i-1)//(leng//N)]!=T[(i-1)//(leng//M)]:
            print(-1)
            break
else:
    print(leng)

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)
K = (N//a)*M
t = (N//a)*(M//a)
flag = 0
k = 0
while (k*t)//(K//N)<N and (k*t)//(K//M)<M:
    if S[(k*t)//(K//N)]!=T[(k*t)//(K//M)]:
        flag = 1
        break
    k += 1
if flag==0:
    print(K)
else:
    print(-1)

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

Solution (Python):
import sys
from math import gcd
input = sys.stdin.readline
N, M = map(int, input().split())
S = list(input())[: -1]
T = list(input())[: -1]
g = gcd(N, M)
ln = N * M // g
x = 0
y = 0
while x < N and (y < M):
  if S[x] != T[y]:
    print(-1)
    exit(0)
  x += ln // M
  y += ln // N
print(ln)

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