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 fractions

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

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

d_N = {}

for n in range(N):
    d = fractions.gcd(n, N)
    d_N[(n // d, N // d)] = n

for m in range(M):
    d = fractions.gcd(m, M)
    k = (m // d, M // d)
    if k in d_N:
        if S[d_N[k]] != T[m]:
            print(-1)
            exit()

L = int(lcm(N, M))
print(L)

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

a = lcm(n,m)
b = gcd(n,m)
if b==1:
  if s[0]==t[0]:
    print(a)
  else:
    print(-1)
else:
  k = int(a//b)
  for i in range(b):
    w = int(n*i//b)
    ww = int(m*i//b)
    if s[w]==t[ww]:
      continue
    else:
      print(-1)
      exit()
  else:
    print(a)

Solution (Python):

from fractions import gcd

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

GCD = gcd(len(S),len(T))
LCM = len(S) * len(T) // GCD
ans = LCM

for i in range(GCD):
    if S[i*len(S)//GCD]!=T[i*len(T)//GCD]:
        ans = -1
        break

print(ans)

Solution (Python):
import sys
from fractions import gcd

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


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


def main():
    N, M = map(int, input().split())
    S = input()
    T = input()
    L = M // gcd(M, N) * N
    G = gcd(M, N)
    n = N // G
    m = M // G

    for i in range(G):
        if S[n * i] == T[m * i]:
            continue
        else:
            print(-1)
            return

    print(L)


if __name__ == "__main__":
    main()

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

Solution (Python):
import fractions

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

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

    L = lcm(N, M)
    ln = L//N
    lm = L//M
    n = {1+i*ln: s for i, s in enumerate(S)}
    m = {1+i*lm: t for i, t in enumerate(T)}
    
    for k in set(n.keys()).intersection(set(m.keys())):
        if n[k] != m[k]:
            return -1

    return L

print(main())

Solution (Python):
import fractions
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
def myAnswer(N:int,M:int,S:str,T:str) -> int:
   a = N//fractions.gcd(N,M)
   b =M // fractions.gcd(N,M)
   
   for i in range(fractions.gcd(N,M)):
      
      if(S [a * i] != T[b * i]):
         return -1
   else:
      return lcm(N,M)

def modelAnswer():
   return
def main():
   N,M = map(int,input().split())
   S = input()
   T = input()
   print(myAnswer(N,M,S,T))
if __name__ == '__main__':
   main()

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

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

g = gcd(N, M)
ans = N*M // g
N //= g
M //= g

if S[0] != T[0] or not all(i == j for i, j in zip(S[N::N], T[M::M])):
    ans = -1
print(ans)

Solution (Python):
import fractions
n,m=map(int,input().split())
s=input()
t=input()
b=0
for i in range(n):
    if (i*m)%n==0 and (i*m)//n<m:
        if not t[(i*m)//n]==s[i]:
            b=1

if b:
    print(-1)
else:
    print(n*m//fractions.gcd(n,m))

Solution (Python):
def gcd(a, b):
    big = max(a, b)
    small = min(a, b)
    
    r = small
    while r != 0:
        r = big % small
        big = small
        small = r
    
    return big
    
def lcm(a, b):
    gcd_num = gcd(a, b)
    return (a // gcd_num) * (b // gcd_num) * gcd_num

def main():
    n, m = map(int, input().split())
    s = input()
    t = input()
    
    a = n // gcd(n, m)
    b = m // gcd(n, m)
    lcm_num = lcm(n, m)
    
    ans = lcm_num
    for i in range(n // a):
        if s[a * i] != t[b * i]:
            ans = -1
            break
    
    print(ans)
    
if __name__ == '__main__':
    main()

Solution (Python):
import fractions
import bisect
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)
S_arr = [0]*N
T_arr = [0]*M
for i in range(1,N):
    S_arr[i] = i*(L//N)
for i in range(1,M):
    T_arr[i] = i*(L//M)
if M <= N:
    for i in range(M):
        index = bisect.bisect_left(S_arr,T_arr[i])
        if S_arr[index] == T_arr[i] and S[index] != T[i]:
            print(-1)
            exit()
else:
    for i in range(N):
        index = bisect.bisect_left(T_arr,S_arr[i])
        if T_arr[index] == S_arr[i] and T[index] != S[i]:
            print(-1)
            exit()

print(L)

Solution (Python):
import sys
import re
import math
import collections
import decimal
import bisect
import itertools
import fractions

import copy





sys.setrecursionlimit(10000001)
INF = sys.maxsize
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))





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

    def multiple(a, b):
        return a * b // euclid(a, b)

    n, m = ns()
    s = list(input())
    t = list(input())

    gcd = multiple(n, m)

    s_idx = [gcd // n * i for i in range(n)]
    t_idx = [gcd // m * i for i in range(m)]
    t_set = set(t_idx)

    for idx in s_idx:
        if idx in t_set:
            if s[idx * n // gcd] != t[idx * m // gcd]:
                print(-1)
                exit(0)

    print(gcd)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
import re
import math
import collections
import decimal
import bisect
import itertools
import fractions

import copy





sys.setrecursionlimit(10000001)
INF = sys.maxsize
MOD = 10 ** 9 + 7

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))





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

    def multiple(a, b):
        return a * b // euclid(a, b)

    n, m = ns()
    s = list(input())
    t = list(input())

    gcd = multiple(n, m)

    s_idx = [gcd // n * i for i in range(n)]
    t_idx = [gcd // m * i for i in range(m)]
    t_set = set(t_idx)

    for idx in s_idx:
        if idx in t_set:
            if s[idx * n // gcd] != t[idx * m // gcd]:
                print(-1)
                exit(0)

    print(gcd)


if __name__ == '__main__':
    main()

Solution (Python):
import functools, fractions
def lcm(a, b):
	return a * b // fractions.gcd(a, b)
def check(L, NM):
    res = []
    for i in range(NM):
        res.append(int(i*(L/NM)+1))
    return res
def check2(x, L, NM):
    return int((x-1)*NM/L)
def main():
    N,M = map(int,input().split())
    S = input()
    T = input()
    L = lcm(N,M)
    ans = L
    a = list(set(check(L, N)) & set(check(L, M)))
    for i in a:
        if S[check2(i, L, N)] != T[check2(i, L, M)]:
            ans = -1
            break
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):
import fractions
def main():
    N, M = (int(_) for _ in input().split())
    S = input()
    T = input()
    g = fractions.gcd(N, M)
    for i in range(N):
        if i % (N//g) == 0 and S[i] != T[M*i//N]:
            print(-1)
            break
    else:
        print(N * M // g)
    return

if __name__ == '__main__':
    main()

Solution (Python):
import math
import fractions
from functools import reduce
import sys
input = sys.stdin.readline


def main():
    n, m = input_list()
    s = input()
    t = input()
    baisuu = lcm_base(n, m)
    ans = {}
    for i in range(1, n+1):
        index = (i - 1) * (baisuu//n) + 1
        ans[index] = s[i-1]

    for i in range(1, m+1):
        index = (i - 1) * (baisuu//m) + 1
        w = t[i-1]
        if index in ans:
            if ans[index] != w:
                print(-1)
                exit(0)
        else:
            ans[index] = w

    print(baisuu)


def input_list():
    return list(map(int, input().split()))

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

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

def gcd(*numbers):
    return reduce(fractions.gcd, numbers)

def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)

if __name__ == "__main__":
    main()

Solution (Python):
from fractions import gcd

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

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

for i in range(0,L,ng*mg):
    Nnum = i//mg
    Mnum = i//ng
    if S[Nnum] != T[Mnum]:
        print(-1)
        exit()

print(L)

Solution (Python):
from fractions import gcd

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

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

for i in range(G):
    Nnum = i*ng
    Mnum = i*mg
    if S[Nnum] != T[Mnum]:
        print(-1)
        exit()

print(L)

Solution (Python):
import fractions
  
def lcm(a,b):
  return (a * b) // fractions.gcd(a, b)

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

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

X = lcm(N,M)

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

for i in range(0,X,m):
  if S[0] != T[0]:
    print(-1)
    break
  elif i % n == 0:
    s = i // n
    t = i // m
    if S[t] != T[s]:
      print(-1)
      break
else:
  print(X)

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)
l = n*m//g
for i, j in zip(s[0:n:n//g], t[0:m:m//g]):
    if i!=j:
        print(-1)
        break
else:
    print(l)

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

lcm = n*m // fractions.gcd(n,m)
ans = -1
ss = lcm // m
ts = lcm // n
j = 0
flg = True
for i in range(0,n,ss):
    if s[i] == t[j] :
        j += ts
        continue
    else:
        flg = False
        break

if flg :
    ans = lcm
print(ans)

Solution (Python):
import sys
readline = sys.stdin.buffer.readline
def even(n): return 1 if n%2==0 else 0
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)
n,m = map(int,readline().split())
s = readline().rstrip().decode('utf-8')
t = readline().rstrip().decode('utf-8')
l = lcm(n,m)
g = gcd(n,m)
flag = 1

for i in range((n-1)//(n//g)+1):
    if not s[i*(n//g)] == t[i*(m//g)]:
        flag = 0
        break


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

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

for i in range(10**9):
    if q*i >= n or p*i >= m:
        print(l)
        exit()
    if s[q*i] != t[p*i]:
        print(-1)
        exit()

Solution (Python):
def gcd(m,n):
    while (m % n != 0):
        n,m = m%n,n
    return(n)

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

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

s = input()
t = input()


g = gcd(m,n)

if(g in [n,m]):
    print(-1)
else:
    x = lcm(m,n)
    a = x // n
    b = x // m
    for i in range(n//b):
        ai = b * i
        bi = a * i
        if(s[ai] != t[bi]):
            print(-1)
            exit()
    print(lcm(m,n))

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

Solution (Python):
n,m=map(int,input().split())
s=input()
t=input()
import fractions
x=n*m//(fractions.gcd(n,m))
n1=x//n
m1=x//m
x1=n1*m1//(fractions.gcd(n1,m1))
if n%m==0:
  for i in range(m):
    if t[i]!=s[n*i//m]:
      print("-1")
      exit()
  print(x)
  exit()
elif m%n==0:
  for i in range(n):
    if s[i]!=t[m*i//n]:
      print("-1")
      exit()
  print(x)
  exit()
else:
  for i in range(x//x1):
    if s[i*x1//n1]!=t[i*x1//m1]:
      print(-1)
      exit()
print(x)

Solution (Python):
from fractions import gcd


N, M = map(int, input().split(" "))
S = input()
T = input()
a, b = M // gcd(N, M), N // gcd(N, M)
GCD = gcd(N, M)

flag = True
for n in range(0, GCD):
    flag &= S[b * n] == T[a * n]

if flag:
    print(N * M // GCD)
else:
    print(-1)

Solution (Python):
from fractions import gcd

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

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

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


s_d = saisho_kobaisu // N
t_d = saisho_kobaisu // M

s_set = set([i * s_d + 1 for i in range(N)])
t_set = set([i * t_d + 1 for i in range(M)])




for idx in s_set.intersection(t_set):
    if (idx-1)//s_d > N or (idx-1)//t_d > M:
        break
    if s[(idx-1)//s_d] != t[(idx-1)//t_d]:
        print(-1)
        exit()

print(saisho_kobaisu)

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

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

from fractions import gcd

gcdnm = gcd(n, m)
L = (n * m) // gcdnm

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


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

i = 1


while l//(L//n)*i < n and l//(L//m)*i <m:
    if s[l//(L//n)*i] != t[l//(L//m)*i]:
        print(-1)
        exit()
    i+=1

print(L)

Solution (Python):
n,m=map(int,input().split())
s=list(input())
t=list(input())
import fractions
x=n*m//fractions.gcd(n,m)
s_lis=[i*x//n+1 for i in range(n)]
t_lis=[i*x//m+1 for i in range(m)]
import bisect
for i in range(n):
    ind=bisect.bisect_left(t_lis,s_lis[i])
    if ind==m:
        continue
    if t_lis[ind]==s_lis[i]:
        if s[i]!=t[ind]:
            print(-1)
            exit()

print(x)

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

ok = True
for i in range(GCD):
    
    if S[i*(N//GCD)] != T[i*(M//GCD)]:
        ok = False

if ok:
    print(LCM)
else:
    print(-1)

Solution (Python):
import sys
from collections import defaultdict

sys.setrecursionlimit(10 ** 7)
f_inf = float('inf')
mod = 10 ** 9 + 7


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


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


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

    L = lcm(n, m)

    X = dict()
    for i in range(n):
        idx = (L // n) * i
        X[idx] = s[i]

    for i in range(m):
        idx = (L // m) * i
        if X.get(idx) != None and X[idx] != t[i]:
            print("-1")
            break
    else:
        print(L)


if __name__ == '__main__':
    resolve()

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

from fractions import gcd

def solve(N,M,S,T):
    g = gcd(N,M)
    for i in range(g):
        if S[N//g*i]!=T[M//g*i]:
            return -1
    ans = N*M//g
    return ans
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)
flag = True
for k in range(g):
  if S[k * N // g] != T[k * M // g]:
    flag = False

if flag:
  print(N * M // g)
else:
  print(-1)

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

g = gcd(N, M)
flag = True
for k in range(g):
  if S[k * N // g] != T[k * M // g]:
    flag = False

if flag:
  print(N // g * M)
else:
  print(-1)

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

from fractions import gcd
g = gcd(n,m)
ans = n*m//g

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

print(ans)

Solution (Python):
import fractions

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

if L == 1:
  print(ans) if S[0] == T[0] else print(-1)
else:
  print(ans) if S[::N//L] == T[::M//L] else print(-1)

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




ans = -1
if n==m:
    if s==t: ans= n
else:
    gcd_nm = gcd(n,m)
    for i in range(gcd_nm):
        if s[n//gcd_nm*i] != t[m//gcd_nm*i]: break
    else: ans = n*m//gcd_nm
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)
ST_idx = set([i*(L//N) for i in range(N)]) & set([i*(L//M) for i in range(M)])

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

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
import fractions
def main():
    n,m=map(int,input().split())
    s=input()
    t=input()
    ans=-1
    if n==m:
        if s==t:
            ans=n
    else:
        gcd_nm=fractions.gcd(n,m)
        for i in range(gcd_nm):
            if s[n//gcd_nm*i]!=t[m//gcd_nm*i]:
                break
        else:
            ans=n*m//gcd_nm
    print(ans)

if __name__=='__main__':
    main()

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

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

n2,m2 = l//n,l//m
g2 = gcd(n2,m2)
l2 = n2*m2//g2

ans = l
for i in range(l//l2):
  if s[i*l2//n2] != t[i*l2//m2]:
    ans = -1
    break
print(ans)

Solution (Python):

















mod = 10**9 + 7

def readInts():
  return list(map(int,input().split()))
def main():
    n,m = readInts()
    s = input()
    t = input()
    from fractions import gcd
    g = gcd(n,m)
    res = n // g * m
    
    n //= g
    m //= g
    ok = True
    for i in range(g):
        
        if s[i*n] != t[i*m]:
            ok = False
    if ok:
        print(res)
    else:
        print(-1)
if __name__ == '__main__':
  main()

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


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

s1=input()

s2=input()

len_moji = lcm(n,m)

len_s1 = []

len_s2 = []

for i in range(n):
    len_s1.append(i*len_moji//n+1)

for i in range(m):
    len_s2.append(i*len_moji//m+1)


count = 0
for ix, vs1 in enumerate(len_s1):
    for jx in range(count,len(len_s2)):
        
        if vs1 < len_s2[jx]:
            count = jx-1
            break
        if vs1 == len_s2[jx]:
            count = jx
            if s1[ix] != s2[jx]:
                print(-1)
                exit()
            break
print(len_moji)

Solution (Python):

import math
import fractions
import bisect
import collections
import itertools
import heapq
import string
import sys
import copy
from decimal import *
from collections import deque
sys.setrecursionlimit(10**7)
MOD = 10**9+7
INF = float('inf') 
def gcd(a,b):return fractions.gcd(a,b) 
def lcm(a,b):return (a*b) // fractions.gcd(a,b) 
def iin(): return int(sys.stdin.readline()) 
def ifn(): return float(sys.stdin.readline()) 
def isn(): return sys.stdin.readline().split() 
def imn(): return map(int, sys.stdin.readline().split()) 
def imnn(): return map(lambda x:int(x)-1, sys.stdin.readline().split()) 
def fmn(): return map(float, sys.stdin.readline().split()) 
def iln(): return list(map(int, sys.stdin.readline().split())) 
def iln_s(): return sorted(iln()) 
def iln_r(): return sorted(iln(), reverse=True) 
def fln(): return list(map(float, sys.stdin.readline().split())) 
def join(l, s=''): return s.join(l) 
def perm(l, n): return itertools.permutations(l, n) 
def perm_count(n, r): return math.factorial(n) // math.factorial(n-r) 
def comb(l, n): return itertools.combinations(l, n) 
def comb_count(n, r): return math.factorial(n) // (math.factorial(n-r) * math.factorial(r)) 
def two_distance(a, b, c, d): return ((c-a)**2 + (d-b)**2)**.5 
def m_add(a,b): return (a+b) % MOD
def lprint(l): print(*l, sep='\n')
def sieves_of_e(n):
    is_prime = [True] * (n+1)
    is_prime[0] = False
    is_prime[1] = False
    for i in range(2, int(n**0.5)+1):
        if not is_prime[i]: continue
        for j in range(i * 2, n+1, i): is_prime[j] = False
    return is_prime


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

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

is_good = True
for i in range(L):
    s_index = i*N//g
    t_index = i*M//g
    if s_index >= N or t_index >= M: break
    if S[s_index] != T[t_index]:
        is_good = False
        break

print(L if is_good else -1)

Solution (Python):
import fractions







import sys

sys.setrecursionlimit(10 ** 5 + 10)


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


def resolve():
    def main():
        N, M = map(int, input().split())
        S = str(input())
        T = str(input())

        lcm = N * M // fractions.gcd(N, M)
        NN = lcm // N
        MM = lcm // M

        lcm2 = NN * MM // fractions.gcd(NN, MM)
        i = 0
        ans = lcm
        while True:
            if lcm2 * i // NN < N and lcm2 * i // MM < M:
                if S[lcm2 * i // NN] != T[lcm2 * i // MM]:
                    ans = -1
                i += 1
            else:
                return ans

    print(main())


resolve()

Solution (Python):
import fractions
def main():
    n,m=map(int,input().split())
    s=input()
    t=input()
    ans=-1
    gcd0=fractions.gcd(n,m)
    lcm=n*m//gcd0
    flg=1
    for i in range(gcd0):
        if s[n*i//gcd0]!=t[m*i//gcd0]:
            flg=0
            break
    if flg==1:
        ans=lcm
    print(ans)
if __name__=="__main__":
    main()

Solution (Python):
n, m = map(int, input().split())
s, t = [input() for i in range(2)]

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

a = len(s)
b = len(t)

g = gcd(a, b)

if all([s[a*i//g]==t[b*i//g] for i in range(g)]):
    print(a*b//g)
else:
    print(-1)

Solution (Python):
n,m=map(int,input().split())
s=input()
t=input()
import fractions
g=fractions.gcd(n,m)
m0=m//g
n0=n//g
i=0
while i*n0<n and i*m0<m:
  if s[i*n0]==t[i*m0]:
    pass
  else:
    print(-1)
    exit()
  i+=1
print(n*m//g)

Solution (Python):
from fractions import gcd

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

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

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

X = {}
for i, s in enumerate(S[1:]):
    idx = (i + 1) * m + 1
    X[idx] = s
    ans = max(ans, idx)

for i, t in enumerate(T[1:]):
    idx = (i + 1) * n + 1
    if (idx in X) and (X[idx] != t):
        print(-1)
        exit(0)
    else:
        ans = max(ans, idx)

print(max(ans, r * m * n))

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

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

ans = f(n,m)

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

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

Solution (Python):
from fractions import gcd
N,M=map(int,input().split())
S=input()
T=input()
L=N*M//gcd(N,M)
p=[]
q=[]

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

Solution (Python):
from fractions import gcd
N,M=map(int,input().split())
S=input()
T=input()
L=N*M//gcd(N,M)
p=[]
q=[]

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

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

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

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

l=lcm(n, m)
index=fractions.gcd(n,m)

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

Solution (Python):
import fractions
N, M = list(map(int, input().split()))
S = input()
T = input()
d = fractions.gcd(N,M)
n = N//d
m = M//d
for i in range(d):
    if S[i*n] != T[i*m]:
        flag = False
        break
    else:
        flag = True
if flag:
  print((N*M)//d)
else:
  print(-1)

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

gcd_n_m = gcd(n,m)
if gcd_n_m == 1 and s[0] == t[0]:
    print(n*m)
else:
    step_s = n // gcd_n_m
    step_t = m // gcd_n_m
    index_s = 0
    index_t = 0
    while index_s < n and index_t < m:
        if s[index_s] != t[index_t]:
            print(-1)
            exit()
        index_s += step_s
        index_t += step_t
    print(n*m//gcd_n_m)

Solution (Python):
from fractions import gcd
N,M=map(int,input().split())
S=input()
T=input()
g=gcd(N,M)
n=N//g
m=M//g
s=[]
t=[]
for i in range(N):
    if i%n==0:
        s.append(S[i])
for j in range(M):
    if j%m==0:
        t.append(T[j])
for x,y in zip(s,t):
    if x!=y:
        print(-1)
        exit()
print(M*N//g)

Solution (Python):
import sys
from fractions import gcd


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


sys.setrecursionlimit(10 ** 9)


def main():
    N, M = map(int, input().split())
    S = input()
    T = input()
    g = gcd(M, N)
    n = N // g
    m = M // g
    s = []
    t = []
    for i in range(N):
        if i % n == 0:
            s.append(S[i])
    for j in range(M):
        if j % m == 0:
            t.append(T[j])
    for x, y in zip(s, t):
        if x != y:
            print(-1)
            return
    print(M * N // g)


if __name__ == "__main__":
    main()

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

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

L = lcm(N, M)
num = lcm(L//N, L//M)

n = (N-1)*(L//N)+1
m = (M-1)*(L//M)+1

if(max(n, m) < num):
    if(S[0] == T[0]):
        print(L)
    else:
        print(-1)
else:
    if(N > M):
        tmp = M//(L//N)
    else:
        tmp = N//(L//M)
    for i in range(tmp):
        if(S[i*L//M] != T[i*L//N]):
            print(-1)
            break
    else:
        print(L)

Solution (Python):
import fractions
import sys
from sys import stdin

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


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


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

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_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(int, 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)

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

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

n, m = map(int, input().split())
s = list(input())
t = list(input())
g = gcd(n, m)
l = lcm(n, m)
x_s = [i for i in range(1, l + 1, m // g)]
x_t = [i for i in range(1, l + 1, n // g)]
j = 0
c = 1
for i in range(len(x_s)):
    while True:
        if j + 1 == len(x_t):
            break
        if x_s[i] > x_t[j]:
            j += 1
        else:
            break
    if x_s[i] == x_t[j]:
        if not s[i] == t[j]:
            c = 0
print(l if c == 1 else -1)

Solution (Python):
from fractions import gcd

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

gc = gcd(N, M)

ans = N*M//gc

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

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

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

Solution (Python):
from collections import defaultdict
from fractions import gcd
N, M = map(int, input().split())
S = input()
T = input()
L = N * M // gcd(N, M)
ds = L // N
dt = L // M
dict_s = defaultdict(str)
dict_t = defaultdict(str)

for i in range(N):
  dict_s[i*ds] = S[i]
  
for i in range(M):
  dict_t[i*dt] = T[i]

for key in dict_s.keys():
  if key in dict_t.keys():
    if dict_s[key] != dict_t[key]:
      print(-1)
      exit()
print(L)

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

Solution (Python):




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


def gcd(a, b):
    if b > a:
        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(n, m)
arr = {}

for i in range(n):
    x = i * (l // n)
    arr[x] = s[i]

for i in range(m):
    x = i * (l // m)
    if x in arr and arr[x] != t[i]:
        print(-1)
        exit()
print(l)

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

Solution (Python):
def main():
    from fractions import gcd

    n, m = map(int, input().split())
    s, t = input(), input()
    l = n * m // gcd(n, m)
    a = [l // n * i + 1 for i in range(n)]
    b = [l // m * i + 1 for i in range(m)]
    c = set(a) & set(b)
    for x in list(c):
        i = a.index(x)
        j = b.index(x)

        if s[i] != t[j]:
            print(-1)
            exit()
    else:
        print(l)


if __name__ == '__main__':
    main()