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

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

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()
    m = lcm(N,M)
    for i in range(M):
        si = i*m//M
        ti = i*m//N
        if si < N and ti < M and S[si] != T[ti]:
            print("-1")
            return
    print(m)

if __name__ == '__main__':
    main()

Solution (Python):
from fractions import gcd
N, M = map(int, input().split())
S = input()
T = input()
L = N*M//gcd(N,M)
a = L//N
b = L//M
c = a*b//gcd(a,b)
i = 0
while i<L:
  if S[i//(L//N)] != T[i//(L//M)]:
    print(-1)
    exit()
  i += c
print(L)

Solution (Python):

from collections import defaultdict
from collections import deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS():return list(map(list, sys.stdin.readline().split()))
def S(): return list(sys.stdin.readline())[:-1]
def IR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = I()
    return l
def LIR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = LI()
    return l
def SR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = S()
    return l
def LSR(n):
    l = [None for i in range(n)]
    for i in range(n):l[i] = SR()
    return l
mod = 1000000007


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

    n,m = LI()
    s = S()
    t = S()
    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)
            return
    print(l)
    return


def B():
    return


def C():
    return


def D():
    return


def E():
    return


def F():
    return


def G():
    return


def H():
    return


if __name__ == "__main__":
    A()

Solution (Python):
def gcd(a,b):
  if a<b:
    a,b=b,a
  if a%b==0:
    return b
  return gcd(b,a%b)
  
N, M = map(int, input().split())
S = input()
T = input()
p = gcd(N, M)
n = N // p
m = M // p
for i in range(p):
  if S[i*n] != T[i*m]:
    print(-1)
    exit()
print((N*M)//p)

Solution (Python):
def main():

    N, M = map(int, input().split())
    S = input()
    T = input()
    p = gcd(N, M)
    n = N // p
    m = M // p
    for i in range(p):
        if S[i*n] != T[i*m]:
            return "-1"
    return p*n*m


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

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

Solution (Python):
import sys
import  math
import bisect
from statistics import *
from collections import *
from operator import itemgetter

from fractions import gcd
def lcm(x, y):
    return (x * y) // gcd(x, y)
stdin = sys.stdin
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline()

n, m = na()
s = input()
t = input()
l = lcm(n, m)
flag = True
ln = l // n
lm = l // m
d = {}
ans = l
for i in range(n):
    d[1 + i * ln] = s[i]
for i in range(m):
    if 1 + i * lm in d.keys():
        if d[1 + i * lm] != t[i]:
            ans = -1
            break
print(ans)

Solution (Python):
from fractions import gcd


N, M = map(int, input().split())
S, T = [input() for _ in range(2)]
L = gcd(N, M)
print(N*M//L if all([S[i*N//L] == T[i*M//L] for i in range(L)]) else -1)

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

def gcd(a, b):
    if b > a:
        a, b = b, a

    if a % b == 0:
        return b

    return gcd(b, a % b)

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

len_l = lcm(N, M)
dict = defaultdict(str)

for i, s in enumerate(S):
    dict[i * len_l//N] = s

for j, t in enumerate(T):
    if dict[j * len_l//M] != "" and dict[j * len_l//M] != t:
        print(-1)
        exit()

print(len_l)

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

def gcd(x,y):
    if x==y:
        return x
    elif x>y:
        r=-1
        while r!=0:
            r=x%y
            x=y
            y=r
        return x
    else:
        r=-1
        while r!=0:
            r=y%x
            y=x
            x=r
        return y

N=n//gcd(n,m)
M=m//gcd(n,m)
f=1
for i in range(gcd(n,m)):
    if s[i*N]!=t[i*M]:
        f=0
if f:
    print(n*m//gcd(n,m))
else:
    print(-1)

Solution (Python):
def main():
    import sys
    input = sys.stdin.readline
    n, m = list(map(int, input().rstrip('\n').split()))
    s = input().rstrip('\n')
    t = input().rstrip('\n')
    import fractions
    lcm = n * m // fractions.gcd(n, m)
    for i in range(0, n * m, lcm):
        if s[i // m] != t[i // n]:
            print(-1)
            exit()
    print(lcm)


if __name__ == '__main__':
    main()

Solution (Python):

import sys, math, fractions, itertools, collections, copy, heapq


def solve(N: int, M: int, S: str, T: str):
    n = fractions.gcd(N, M)
    x = N * M // n

    flag = True
    for i in range(n):
        if S[i * x // M] == T[i * x // N]:
            pass
        else:
            flag = False
            break

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

    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    M = int(next(tokens))  
    S = next(tokens)  
    T = next(tokens)  
    solve(N, M, S, T)

if __name__ == '__main__':
    main()

Solution (Python):
from fractions import gcd

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

n = gcd(N, M)

x = N * M // n


flag = True
for i in range(n): 
    
    
    if S[i * x // M] == T[i * x // N]:
        pass
    else:
        flag = False
        break

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

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

def main():
    N, M = map(int, input().split())
    s = input().strip()
    t = input().strip()
    if M > N:
        tmp = s
        s = t
        t = tmp
        tmp = N
        N = M
        M = tmp
    
    gcd_ = gcd(N, M)
    len_ = N * (M//gcd_)
    tmp1 = len_ // N
    tmp2 = len_ // M
    
    ok = True
    for i in range(0, len_, tmp1 * (tmp2//gcd(tmp1, tmp2))):
        
        if s[i//tmp1] != t[i//tmp2]:
            ok = False
            break
    if ok:
        print(len_)
    else:
        print(-1)

if __name__ == "__main__":
    main()

Solution (Python):
from fractions import gcd


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

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 fractions
N,M = map(int,input().split())
S = input()
T = input()

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

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

Solution (Python):
from fractions import gcd


def lcm(a, b):
    """
    aとbの最小公倍数を計算します。
    """
    return a * b // gcd(a, b)


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

ans = lcm(N, M)

c = dict()
for i in range(N):
    c[i * ans // N] = S[i]
for i in range(M):
    val = c.get(i * ans // M)
    if val is not None and val != T[i]:
        print(-1)
        exit(0)
print(ans)

Solution (Python):
def factorize2(n):
    """
    nの値を素因数分解し、素因数とその指数をtupleにまとめたリストを返す
    e.g.
    [(2, 2), (5, 1)]
    """
    b = 2
    fct = []
    while b * b <= n:
        cnt = 0
        while n % b == 0:
            cnt += 1
            n //= b
        if cnt > 0:
            fct.append((b, cnt))
        b += 1
    if n > 1:
        fct.append((n, 1))
    return fct


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

d = dict()
for num, pow in factorize2(N):
    d[num] = pow
for num, pow in factorize2(M):
    if d.get(num) is None:
        d[num] = pow
    elif d[num] < pow:
        d[num] = pow
ans = 1
for num, pow in d.items():
    ans *= num ** pow

c = dict()
for i in range(N):
    c[i * ans // N] = S[i]
for i in range(M):
    val = c.get(i * ans // M)
    if val is not None and val != T[i]:
        print(-1)
        exit(0)
print(ans)

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

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

Solution (Python):


from fractions import gcd

n,m=map(int,input().split())
s=input()
t=input()
lcd=(n*m)//gcd(n,m)
x={}
aa=(lcd//n)
bb=(lcd//m)
for i in range(n):
    a=i*aa
    x[a]=s[i]

for i in range(m):
    b=i*bb
    if b in x and x[b]!=t[i]:
        print(-1)
        exit()
    
print(lcd)

Solution (Python):



import sys
import math
import bisect
sys.setrecursionlimit(1000000000)
from heapq import heappush, heappop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7

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,sys.stdin.readline().split())
s = input()
t = input()
l = lcm(n,m)
a,b = n//gcd(n,m),m//gcd(n,m)
for i in range(min(n//a,m//b)):
    if s[a*i] != t[b*i]:
        print(-1)
        quit()
print(l)

Solution (Python):
from fractions import gcd
N,M=map(int,input().split())
S=input()
T=input()
s=(M//gcd(N,M))
t=(N//gcd(N,M))
SS=[i*s for i in range(N)]
TT=[j*t for j in range(M)]
p,q=0,0
ans=N*s
while True:
    if SS[p]==TT[q]:
        if S[p]!=T[q]:ans=-1
        p+=1
        q+=1
    elif SS[p]>TT[q]:
        q+=1
    else:
        p+=1
    if p==N or q==M:
        break
print(ans)

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
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)

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

a = lcm(N, M)
b = lcm(a//N, a//M)

l = [0]
tmp = 0
while tmp < a:
    tmp += b
    if tmp < a:
        l.append(tmp)



check = 0

for i in range(len(l)):

    if S[l[i]//(a//N)] == T[l[i]//(a//M)]:
        pass
    else:
        check = 1 

if check == 0:
    ans = a
else:
    ans = -1

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(100000000)
def input():
    return sys.stdin.readline()[:-1]
from bisect import *
from collections import *
from heapq import *
from math import *

N, M = map(int, input().split())
S, T = input(), input()
gcd = lambda a, b: a if b == 0 else gcd(b, a%b)
g = gcd(N, M)
n, m = N//g, M//g
for i in range(min(N//n, M//m)):
    if S[n*i] != T[m*i]:
        print(-1)
        exit()
print(N*M//g)

Solution (Python):
import fractions

N, M = map(int, input().split())
S = input()
T = input()
gcd = fractions.gcd(N, M)
lcm = N*M // gcd
ans = lcm


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

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


def main():
    N, M = map(int, input().split())
    s = input()
    t = input()
    d = gcd(N, M)
    for i in range(d):
        if s[i*N//d] != t[i*M//d]:
            print(-1)
            return
    print(N*M//d)


if __name__ == "__main__":
    main()

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


def l_c_m(x, y):
    return x * y // g_c_d(x, y)


a, b = map(int, input().split())
c = input()
d = input()
lcm = l_c_m(a, b)
gcd = g_c_d(a, b)
for i in range(0, gcd):
    if c[i * a // gcd] != d[i * b // gcd]:
        print(-1)
        exit()
print(lcm)

Solution (Python):

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


def main():
    n, m = tuple(map(int, input().rstrip().split()))
    S, T = tuple(input().rstrip() for _ in range(2))
    g = gcd(n, m)
    flg = S[:: n // g] == T[:: m // g]
    print(n // g * m if flg else -1)


if __name__ == "__main__":
    main()

Solution (Python):

from fractions import gcd


def main():
    n, m = tuple(map(int, input().rstrip().split()))
    S, T = tuple(input().rstrip() for _ in range(2))
    g = gcd(n, m)
    flg = S[:: n // g] == T[:: m // g]
    print(n // g * m if flg else -1)


if __name__ == "__main__":
    main()

Solution (Python):

from fractions import gcd


def main():
    n, m = tuple(map(int, input().rstrip().split()))
    S, T = tuple(input().rstrip() for _ in range(2))
    l = n // gcd(n, m) * m
    x = {}
    for i in range(n):  
        j = (l // n) * i
        x[j] = S[i]
    for i in range(m):  
        j = (l // m) * i
        if j in x and x[j] != T[i]:
            print(-1)
            break
    else:
        print(l)


if __name__ == "__main__":
    main()

Solution (Python):
from sys import exit
import math
from fractions import gcd

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

N,M=map(int,input().split())
S=input()
T=input()
if S[0] != T[0]:
    print("-1")
    exit()
if N==M:
    if S==T:
        print(N)

    else:
        print(-1)
    exit()
    
if N<M:
    N,M=M,N
    S,T=T,S
    


if(N%M==0):
    S2=""
    for i in range(N):
        if i%(N//M)==0 :
            S2+=S[i]
            
    if S2==T:
        print(N)
    else:
        print(-1)
    exit()

else:
    g=gcd(N,M)
    S2=""
    for i in range(N):
        if i%(N//g)==0 :
            S2+=S[i]
    T2=""
    for i in range(M):
        if i%(M//g)==0 :
            T2+=T[i]
    if S2==T2:
        print(lcm(N,M))
    else:
        print(-1)

Solution (Python):
import fractions

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

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

N_step=L//N
M_step=L//M
X_step=N_step*M_step//fractions.gcd(N_step,M_step)

flag=True
for i in range(L//X_step):
    if S[M_step*i]!=T[N_step*i]:
        flag=False

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

Solution (Python):
from fractions import gcd

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

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

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

print(lcm)

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 int(x/gcd(x, y)*y)

lenx = lcm(N,M)

s_list = list(S)
t_list = list(T)

baisuu_s = int(lenx/N)
baisuu_t = int(lenx/M)
def check():
    for i in range(0,lenx,baisuu_s):
        if i % baisuu_s==0 and i%baisuu_t == 0:
            if s_list[int(i/baisuu_s)] == t_list[int(i/baisuu_t)]:
                pass
            else:
                return False
    return True

if check():
    print(lenx)
else:
    print(-1)

Solution (Python):

from collections import defaultdict, deque
import math
from math import factorial
import fractions
import re

BIGNUM = 10 ** 9 + 7

def main():
    L, N = map(int, input().split())
    S = list(input())
    T = list(input())
    
    lcm = len(S) * len(T) // fractions.gcd(len(S), len(T))
    gcd = fractions.gcd(len(S), len(T))
    S_unit = len(S) // gcd
    T_unit = len(T) // gcd

    for i in range(gcd):
        if S[i*S_unit] != T[i*T_unit]:
            print(-1)
            return
    print(lcm)

if __name__ == '__main__':
    main()

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

Solution (Python):
N,M=list(map(int,input().strip().split(' ')))
A=input()
B=input()
def gcd(a,b):
    if a>b:
        a,b=b,a
    if b%a==0:
        return a
    return gcd(b%a,a)
g=gcd(M,N)
m=M//g
n=N//g
flag=1
for r in range(g):
    if A[n*r]!=B[m*r]:
        flag=0

if flag==1:
    print(g*m*n)
else:
    print(-1)

Solution (Python):
from fractions import gcd

def main():
    n,m = map(int, input().split())
    s = input()
    t = input()
    g = gcd(n,m)
    smatch = []
    tmatch = []
    flag = True
    for i in range(g):
        smatch.append(s[i*(n//g)])
        tmatch.append(t[i*(m//g)])
    for k,l in zip(smatch,tmatch):
        if k != l:
            flag = False

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


main()

Solution (Python):
from fractions import gcd

N, M = map(int, input().split()) 
S = input()
T = input()
Gcd = gcd(N, M)
Np = N // Gcd
Mp = M // Gcd

ans = Gcd * Mp * Np
for g in range(Gcd):
    if S[g*Np] != T[g*Mp]:
        ans = -1
        break

print(ans)

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

Solution (Python):
from sys import stdin
import fractions
N,M = [int(x) for x in stdin.readline().rstrip().split()]
S = (stdin.readline().rstrip())
T = (stdin.readline().rstrip())
g = fractions.gcd(N,M)
def lcm(a, b):
    return a * b / fractions.gcd(a, b)
flag = True
for i in range(g):
    if S[(i*N)//g] != T[(i*M)//g]:
        flag = False
        break
if flag:
    print(int(lcm(N,M)))
else:
    print(-1)

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

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

gc = gcd(n,m)
lcm = n * m // gc
s = input()
t = input()

if s[::n//gc] == t[::m//gc]:
  print(lcm)
else:
  print(-1)

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

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

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


def LCM(a, b):
    return a * b // GCD(a, b)

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

l = LCM(n, m) 
k = l//GCD(n, m) 
flag = True
for i in range(l//k):
    if s[k*i//(l//n)] != t[k*i//(l//m)]:
        flag = False

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

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

def solve(n, m, s, t):
    if n < m:
        s, t = t, s
        n, m = m, n
    if n % m == 0:
        l = n
    else:
        l = n * m // gcd(n, m)
    D = {}
    for i in range(n):
        D[i*l//n] = s[i]
    for i in range(m):
        k = i*l//m
        if (k in D) and (D[k] != t[i]):
            return -1
    return l

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

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

Solution (Python):

"""
A - Two Abbreviations
https://atcoder.jp/contests/agc028/tasks/agc028_a

"""
import sys

from fractions import gcd

def solve(N, M, S, T):
    lcm = N * M // gcd(N, M)
    res = dict()
    for i, s in zip(range(0, lcm+1, lcm//N), S):
        res[i] = s
    for j, t in zip(range(0, lcm+1, lcm//M), T):
        if j in res and res[j] != t:
            return -1
    return lcm


def main(args):
    N, M = map(int, input().split())
    S = input()
    T = input()
    ans = solve(N, M, S, T)
    print(ans)


if __name__ == '__main__':
    main(sys.argv[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)
n = N//gcd(N,M)
m = M//gcd(N,M)
for k in range(gcd(N,M)):
    if S[k*n] != T[k*m]:
        print(-1)
        exit()
print(L)

Solution (Python):
from fractions import gcd
str_1_len, str_2_len = map(int, input().split())
string_1 = input()
string_2 = input()

gr_com_div = gcd(str_1_len, str_2_len)
low_com_multpl = int(str_1_len * str_2_len / gr_com_div)
flg = True

for i in range(gr_com_div):
    if string_1[i*str_1_len//gr_com_div] == string_2[i*str_2_len//gr_com_div]:
        continue
    else:
        flg = False
if flg:
    print(low_com_multpl)
else:
    print(-1)

Solution (Python):
import fractions

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

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

si = 0
ti = 0

for _ in range(g):
    if S[si] != T[ti]:
        print(-1)
        break
    si += N // g
    ti += M // g
else:
    print(h)

Solution (Python):
from fractions import gcd
from math import sqrt
from heapq import *
from math import factorial
from collections import defaultdict

N,M=map(int,input().split())
S=input()
T=input()
g=gcd(N,M)
m=(N//g)*(M//g)*g
a=0
b=0
A=m//N
B=m//M
t=True
while(a<N):
    if S[a]==T[b]:
        a+=B
        b+=A
    else:
        print(-1)
        quit()
print(m)

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


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

lcm = (n * m) // gcd(n, m)
sSub = [s[i] for i in range(0, n, lcm // m)]
tSub = [t[j] for j in range(0, m, lcm // n)]

if sSub == tSub:
    print(lcm)
else:
    print(-1)

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

S = input()
T = input()


arr1 = [0]*(max(N, M) + 1)
arr2 = [0]*(max(N, M) + 1)


def factoring(arr, tmp):
    i = 1
    while i < tmp:
        i += 1
        if tmp % i == 0:
            tmp = tmp // i
            arr[i] += 1
            i = 1
    
factoring(arr1, tmp=N)
factoring(arr2, tmp=M)

U = 1
for i in range(2, max(N, M)+1):
    tmp = max(arr1[i], arr2[i])
    if tmp != 0:
        U *= i**tmp
V = 1
for i in range(2, max(N, M)+1):
    tmp = min(arr1[i], arr2[i])
    if tmp != 0:
        V *= i**tmp


def good_str(N, M, S, T):
    n = 0
    m = 0
    while n < N and m < M:
        if M*n == N*m:
            if S[n] != T[m]:
                return False
        if M*n > N*m:
            m += 1
        else:
            n += 1
    return True


if good_str(N, M, S, T):
    print(U)
else:
    print(-1)

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


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

L = lcm(N,M)
m1 = L // N
m2 = L // M
mlcm = lcm(m1,m2)
idx = 0
flag = True
while True:
    sid = mlcm*idx//m1
    tid = mlcm*idx//m2
    if sid >= N or tid >= M: break    
    if S[sid] != T[tid]:
        flag = False
        break
    idx += 1

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

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

Solution (Python):
from fractions import gcd

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

s = input()
t = input()

div = gcd(n, m)
div_n = n // div
div_m = m // div

if s[::div_n] == t[::div_m]:
    print(n * m // div)
else:
    print(-1)

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

Solution (Python):
import fractions
n, m = [int(item) for item in input().split()]
s = input().rstrip()
t = input().rstrip()

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

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

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

Solution (Python):
def gcd(a, b):
    if a < b:
        a, b = b, a
    if b == 0:
        return a
    c = a % b
    return gcd(b, c)
  
N,M = [ int(it) for it in input().split() ]
S = input()
T = input()
P = gcd(N,M)
NP = N//P
MP = M//P
NPMP = NP*MP
flag = True
for i in range( P ):
  if ( S[NP*i] != T[MP*i] ):
    flag = False

print (NPMP*P) if flag else print (-1)

Solution (Python):
gcd=lambda a,b: a if b==0 else gcd(b,a%b)
n,m=map(int,input().split())
s=input()
t=input()
d=gcd(n,m)
a = n*m//d if s[::n//d]==t[::m//d] else -1
print(a)

Solution (Python):
gcd = lambda a,b: a if b==0 else gcd(b,a%b)
n,m = map(int,input().split())
s = input()
t = input()
d = gcd(n,m)
if s[::n//d]==t[::m//d]:
    print(n*m//d)
else:
    print(-1)

Solution (Python):
gcd = lambda a,b: a if b==0 else gcd(b,a%b)
n,m = map(int,input().split())
s = input()
t = input()
a = m//gcd(n,m)
b = n//gcd(n,m)
if s[::b]==t[::a]:
    print(n*m//gcd(n,m))
else:
    print(-1)

Solution (Python):
from fractions import gcd

N, M = map(int, input().split())
s = input()
t = input()
g = gcd(N, M)
n, m = N//g, M//g

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

Solution (Python):
def gcd(a,b):
	x,y = min(a,b), max(a,b)
	while x*y>0:
		x,y = y%x,x
	return y

N,M=map(int,input().split())
S=input()
T=input()
g=gcd(N,M)
p,q=M//g,N//g
print((N//g)*M) if S[0::q]==T[0::p] else print('-1')

Solution (Python):
def gcd(a,b):
	x,y = min(a,b), max(a,b)
	while x*y>0:
		x,y = min(x,y), max(x,y)
		x,y = y-x,x
	return y

N,M=map(int,input().split())
S=input()
T=input()
g=gcd(N,M)
p,q=M//g,N//g
print((N//g)*M) if S[0::q]==T[0::p] else print('-1')

Solution (Python):



import fractions
import sys
from collections import defaultdict

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

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

L = lcm(N, M)

dp = defaultdict(lambda: -1)

for i, s in enumerate(S):
    dp[i*L//N] = s

for i, t in enumerate(T):
    if dp[i*L//M] != -1:
        if dp[i*L//M] != t:
            print(-1)
            sys.exit()
print(L)

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

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

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

tmp = T
ss = L//N
tt = L//M
for i in range(N):
    if (i * ss) % tt == 0:
        if S[i] != T[(i*ss)//tt]:
            print('-1')
            quit()

print(L)

Solution (Python):
import fractions
n,m=map(int,input().split())
s=input()
t=input()
l=n*m//fractions.gcd(n,m)
p=l//n*l//m//fractions.gcd(l//n,l//m)
ss,tt="",""
for i in range(l//p):
  ss+=s[i*p*n//l]
  tt+=t[i*p*m//l]
print(l if ss==tt else -1)

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

GCD = gcd(N, M)
LCM = int(N * M / GCD)
flg = True

for i in range(GCD):
    if S[i*N//GCD] == T[i*M//GCD]:
        continue
    else:
        flg = False
if flg:
    print(LCM)
else:
    print(-1)

Solution (Python):

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

def gcd(GCD1,GCD2):
    x = min(GCD1,GCD2)
    y = max(GCD1,GCD2)
    if y%x == 0:
        return x
    else:
        return gcd(x,y%x)
MINA=int(N*M/gcd(N,M))
n=int(MINA/N)
m=int(MINA/M)
flag=0
nn=int(M/n)
mm=int(N/m)
SS=[]
TT=[]
for i in range(mm):
    SS.append(Slist[i*m])
for i in range(nn):
    TT.append(Tlist[i*n])
if SS != TT:
    flag=1
if flag==0:
    print(MINA)
else:
    print(-1)

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

n,m=map(int,input().split())
s=input()
spos=[0]*n
t=input()
tpos=[0]*m
l=n*m//gcd(n,m)
g=gcd(n,m)
ldic={}
flag=True
for i in range(n):
  ldic[1+i*m//g]=s[i]  
for i in range(m):
  if 1+i*n//g in ldic:
    if ldic[1+i*n//g]!=t[i]:
      flag=False
if flag:
  print(l)
else:
  print(-1)

Solution (Python):
import sys
from fractions import gcd

n, m = list(map(int, input().split()))
lcm = n * m / gcd(n, m)

s = input()
t = input()

d = {}
for i, e in enumerate(s):
    d[(lcm / n) * i + 1] = e

for i, e in enumerate(t):
    if ((lcm / m) * i + 1) in d and d[(lcm / m) * i + 1] != e:
        print(-1)
        sys.exit()

print(int(lcm))

Solution (Python):
import fractions

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

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

ng = s[::n//g]
mg = t[::m//g]

if ng == mg:
    print(l)
else:
    print(-1)

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

from fractions import gcd
g = gcd(N,M)
n = N//g
m = M//g

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