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



Sample input:
3 2
acp
ae


Sample output:
6

Submission status: Runtime Error

Solution code:
# python3.4.2用
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()) #整数map取得
def imnn(): return map(lambda x:int(x)-1, sys.stdin.readline().split()) #整数-1map取得
def fmn(): return map(float, sys.stdin.readline().split()) #浮動小数点map取得
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 # 2点間の距離
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)

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

X = list('@')*L

for i in range(1, N+1):
    index = i*(L//N)
    if index >= N: break
    if X[index] == '@':
        X[index] = S[i]

is_good = True
for i in range(1, M+1):
    index = i*(L//M)
    if index >= M: break
    if X[index] == '@':
        X[index] = T[i]
    else:
        if X[index] != T[i]:
            is_good = False
            break
print(L if is_good else -1)

Submission status: Runtime Error

Solution code:
import math
# import numpy as np  # Pythonのみ！
# from operator import xor
# import re
# from scipy.sparse.csgraph import connected_components  # Pythonのみ！
# ↑cf.  https://note.nkmk.me/python-scipy-connected-components/
# from scipy.sparse import csr_matrix
# import string
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 // math.gcd(N, M)

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

    print(main())


resolve()

Submission status: Runtime Error

Solution code:
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 // math.gcd(N, M)

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

    print(main())


resolve()

Submission status: Runtime Error

Solution code:
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()

Submission status: Runtime Error

Solution code:
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()

Submission status: Runtime Error

Solution code:
from fractions import gcd
N,M=map(int,input().split())
S=input()
T=input()
ans=L
L=N*M//gcd(N,M)

U=[]
V=[]

#1個目
for i in range(N):
  U.append( [i*(L//N),S[i]])
#2個目
for i in range(M):
  V.append( [i*(L//M),T[i]])
#print(U)
#print(V)
for i in U:
  for j in V:
    if i[0]==j[0] and i[0]!=j[1]:
      print(-1)
      exit()


#  U[i*(L//N)]=S[i]
#  if U[j*(L//M)]!="#" and U[j*(L//M)]!=T[j]:
print(ans)

Submission status: Runtime Error

Solution code:
from fractions import gcd
N,M=map(int,input().split())
S=input()
T=input()
ans=L
L=N*M//gcd(N,M)

U=[]
V=[]

#1個目
for i in range(N):
  U.append( [i*(L//N),S[i]])
#2個目
for i in range(M):
  V.append( [i*(L//M),T[i]])
#print(U)
#print(V)
for i in U:
  for j in V:
    if i[0]==j[0] and i[0]!=j[1]:
      print(-1(
      exit


#  U[i*(L//N)]=S[i]
#  if U[j*(L//M)]!="#" and U[j*(L//M)]!=T[j]:
print(ans)

Submission status: Runtime Error

Solution code:
import math
[n,m] = list(map(int, input().split(" ")))
s = input()
t = input()
g = math.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))

Submission status: Runtime Error

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

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

l=lcm(n, m)
index=fractions.gcd(n,m)
#print(indexn,indexm)
for i in range(index):
    #print(i)
    if s[n//index*i]!=t[m//index*i]:
        print(-1)
        break
else:
    print(l)

Submission status: Runtime Error

Solution code:
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)
ans=[0]*(l*2)

for i in range(n):
    index=l//n*i+1

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

Submission status: Runtime Error

Solution code:
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)
ans=[0]*(l+2)

for i in range(n):
    index=l//n*i+1

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

Submission status: Runtime Error

Solution code:
import math
N, M = list(map(int, input().split()))
S = input()
T = input()
d = math.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)

Submission status: Runtime Error

Solution code:
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)
ans=[0]*(l+1)

for i in range(n):
    index=l//n*i+1

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

Submission status: Runtime Error

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

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

l=lcm(n, m)
ans=[0]*(l+1)

for i in range(n):
    index=l//n*i+1

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

Submission status: Runtime Error

Solution code:
import math
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) // math.gcd(x, y)


if max(n, m) % min(n, m) == 0:
    print(-1)
else:
    print(lcm(n, m))

Submission status: Runtime Error

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

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

len_x = lcm(N, M)
n = [""]*(len_x)    
m = [""]*(len_x)

for i in range(len(S)):
    n[(len_x//N)*i] = S[i]
    
for i in range(len(T)):    
    m[(len_x//M)*i] = T[i]
for i in range(len_x):
    if(n[i] == "" or m[i] == ""):
        continue     
    if(n[i] != m[i]):
        print(-1)
else:
    print(len_x)

Submission status: Runtime Error

Solution code:
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)
X = [""]*L

for i, s in enumerate(S):
	if i*(L//N) <= L-1:
		X[i*(L//N)] = s

for i, t in enumerate(T):
	if i*(L//M) <= L-1 and X[i*(L//M)] and X[i*(L//M)] != t:
		print(-1)
		break
else:
	print(L)

Submission status: Runtime Error

Solution code:
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)
X = [""]*L

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

for i, t in enumerate(T):
	if X[i*(L//M)] and X[i*(L//M)] != t:
		print(-1)
		break
else:
	print(L)

Submission status: Runtime Error

Solution code:
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(lcm//max(N, M)):
    if S[N//gc*i] != T[M//gc*i]:
        ans = -1
        break
                
print(ans)

Submission status: Runtime Error

Solution code:
from fractions import gcd

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

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

ans = lcm

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

Submission status: Runtime Error

Solution code:
from fractions import gcd

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

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

ans = lcm

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

Submission status: Runtime Error

Solution code:
import math

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

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

ans = lcm

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

Submission status: Runtime Error

Solution code:
N,M=map(int,input().split())
S=input()
T=input()
from math 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)

Submission status: Runtime Error

Solution code:
from fractions import gcd
def lcm(a,b):
    return a * b // gcd(a,b)

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

s = s[0] + s
t = t[0] + t
l = lcm(n, m)
for k in range(gcd(n, m) - 1):
    if s[k*n] != t[k*m]:
        print(-1)
        break
else:
    print(l)

Submission status: Runtime Error

Solution code:
from math import gcd
def lcm(a,b):
    return a * b // gcd(a,b)

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

s = s[0] + s
t = t[0] + t
l = lcm(n, m)
for k in range(gcd(n, m) - 1):
    if s[k*n] != t[k*m]:
        print(-1)
        break
else:
    print(l)

Submission status: Runtime Error

Solution code:
# たぶん最小の値は最小公倍数になりそう

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 = [0] * l

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

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

Submission status: Runtime Error

Solution code:
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)

Submission status: Runtime Error

Solution code:
def main():
    from math import gcd
    import sys

    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()

Submission status: Runtime Error

Solution code:
import fractions


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


N, M = map(int, input().split())
S = input()
T = input()
length = lcm(N,M)
    
for i in range(length):
    if i%(length//N)==0 and i%(length//M)==0:
        if S[i//(length//N)] != T[i//(length//M)]:
            return -1
return length

Submission status: Runtime Error

Solution code:
#
# N M
# S
# T
#
# find X (length L, LはN, Mで割り切れる (最小公倍数))
#
# e.g.
# 3 2
# acp
# ae
#
# X
# - 
# - 1, L/N+1, 2L/N+1, ... はSになる
# - 1, L/M+1, 2L/M+1, ... はTになる

from fractions import gcd

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

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

# 仮の文字列 (中身は何でもいい)
ans = [S[0]] + ["-"] * (L - 1)

# Sを置く
for i in range(N):
    ans[i * L // N] = S[i]

# print(ans)

# Tを置く
# 既にSが入っている場合，Tと整合するか確認する
for i in range(M):
    index = i * L // M
    if ans[index] != "-":
        if ans[index] != T[i]:
            print(-1)
            exit()
        else:
            ans[index] = T[i]
    else:
        ans[index] = T[i]


print(L)

Submission status: Runtime Error

Solution code:
import fractions
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
N, M = map(int, input().split())
S = input()
T = input()
if S[0] != T[0]:
    print(-1)
    exit()
L = lcm(N,M)
ans = ['']*L
ans[0] = S[0]
for i in range(1,N):
    ans[i*(L//N)] = S[i]
for i in range(1,M):
    if ans[i*(L//M)] == '' or ans[i*(L//M)] == T[i]:
        ans[i*(L//M)] = T[i]
    else:
        print(-1)
        exit()
print(L)

Submission status: Runtime Error

Solution code:
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)
ans = ['']*L
ans[0] = S[0]
for i in range(1,N):
    ans[i*(L//N)] = S[i]
for i in range(1,M):
    if ans[i*(L//M)] == '' or ans[i*(L//M)] == T[i]:
        ans[i*(L//M)] = T[i]
    else:
        print(-1)
        exit()
print(L)

Submission status: Runtime Error

Solution code:
import fractions
N,M=map(int,input().split())
S=input()
T=input()
lcm=(N*M)/fractions.gcd(N,M)
num=0
s=[]
t=[]
flag=1
sindex=0
tindex=0
num=lcm
st=[""]*int(num)
for j in range(N):
    s.append([S[j],int(1+(num//N)*j)-1])
for j in range(M):
    t.append([T[j], int(1 + (num // M) * j) - 1])
#print(s,t)
while (sindex<N)and(tindex<M):
    #print(sindex,tindex)
    if s[sindex][1]==t[tindex][1]:
        if s[sindex][0]!=t[tindex][0]:
            flag=0
            break
        sindex=sindex+1
        tindex=tindex+1
    elif s[sindex][1]<t[tindex][1]:
        sindex=sindex+1
    else:
        tindex = tindex + 1
    #input()
if flag==0:
    print("-1")
else:
    print(len(st))

Submission status: Runtime Error

Solution code:
import fractions
N,M=map(int,input().split())
S=input()
T=input()
lcm=(N*M)/fractions.gcd(N,M)
num=0
s=[]
t=[]
flag=1
for i in range(1):
    num=lcm*(i+1)
    st=[""]*int(num)
    for j in range(N):
        s.append([S[j],int(1+(num//N)*j)-1])
        st[int(1 + (num // N) * j)-1]=S[j]
    for j in range(M):
        t.append([T[j], int(1 + (num // M) * j) - 1])
        if st[int(1+(num//M)*j)-1]=="":
            st[int(1 + (num // M) * j)-1]=T[j]
        elif st[int(1+(num//M)*j)-1]!=T[j]:
            flag=0
            break
    if flag==1:
        break
    #print(s,t)
    s=[]
    t=[]
if flag==0:
    print("-1")
else:
    print(len(st))

Submission status: Runtime Error

Solution code:
import fractions
N,M=map(int,input().split())
S=input()
T=input()
lcm=(N*M)/fractions.gcd(N,M)
num=0
s=[]
t=[]
flag=1
for i in range(1):
    num=lcm*(i+1)
    st=[""]*int(num)
    for j in range(N):
        if st[int(1+(num//N)*j)-1]=="":
            st[int(1 + (num // N) * j)-1]=S[j]
        elif st[int(1+(num//N)*j)-1]!=S[j]:
            flag=0
            break
    for j in range(M):
        if st[int(1+(num//M)*j)-1]=="":
            st[int(1 + (num // M) * j)-1]=T[j]
        elif st[int(1+(num//M)*j)-1]!=T[j]:
            flag=0
            break
    if flag==1:
        break
    #print(s,t)
    s=[]
    t=[]
if flag==0:
    print("-1")
else:
    print(len(st))

Submission status: Runtime Error

Solution code:
import fractions
N,M=map(int,input().split())
S=input()
T=input()
lcm=(N*M)/fractions.gcd(N,M)
num=0
s=[]
t=[]
flag=1
for i in range(max(N,M)):
    num=lcm*(i+1)
    st=[""]*int(num)
    for j in range(N):
        if st[int(1+(num//N)*j)-1]=="":
            st[int(1 + (num // N) * j)-1]=S[j]
        elif st[int(1+(num//N)*j)-1]!=S[j]:
            flag=0
            break
    for j in range(M):
        if st[int(1+(num//M)*j)-1]=="":
            st[int(1 + (num // M) * j)-1]=T[j]
        elif st[int(1+(num//M)*j)-1]!=T[j]:
            flag=0
            break
    if flag==1:
        break
    #print(s,t)
    s=[]
    t=[]
if flag==0:
    print("-1")
else:
    print(len(st))

Submission status: Runtime Error

Solution code:
import fractions

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

Submission status: Runtime Error

Solution code:
a,s=map(int,input().split())
sa,ss=[input() for i in range(2)]
if a<s:
    a,s=s,a
    sa,ss=ss,sa
from math import gcd
g=gcd(a,s)
x,y=a//g,s//g
for i in range(1,s//x):
    if sa[y*i]!=ss[x*i]:print(-1);break
else:print(x*s)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

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

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

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

lcm = lcm(N,M)
L = lcm

X1_list = [" "]*L
X2_list = [" "]*L

X1_list[0] = S[0]
for i in range(1,N):
    X1_list[ int(i*(L/N)+1) - 1 ] = S[i]

X2_list[0] = T[0]   
for i in range(1,M):
    X2_list[ int(i*(L/M)+1) - 1 ] = T[i]

for i in range(L):
    if X1_list[i] != " " and X2_list[i] != " " and X1_list[i] != X2_list[i]:
        print(-1)
        break
else:
    print(L)

Submission status: Runtime Error

Solution code:
from fractions import gcd

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

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

L1 = [0]
L2 = [0]

from collections import Counter
c = Counter()

for i in range(1, N):
    t = i * (L // N) + 1
    L1.append(t-1)
    c[t-1] += 1

for i in range(1, M):
    t = i * (L // M) + 1
    L2.append(t-1)
    c[t-1] += 1

common = []
dic = dict()
for k, v in c.items():
    if v == 2:
        common.append(k)
        dic[k] = [None, None]

l1_ind = 0  # N-1まで
l2_ind = 0  # M-1まで
for ci in common:
    for i in range(l1_ind, N):
        if L1[i] == ci:
            dic[ci][0] = i
            l1_ind = i
            break

    for i in range(l2_ind, M):
        if L2[i] == ci:
            dic[ci][1] = i
            l2_ind = i
            break

# print(L1)
# print(L2)
# print(common)
# print(dic)

ans = True
for si, ti in dic.values():
    if S[si] != T[ti]:
        ans = False


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

Submission status: Runtime Error

Solution code:
from fractions import gcd

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

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

L1 = [1]
L2 = [1]
for i in range(1, N):
    t = i * (L // N) + 1
    L1.append(t)

for i in range(1, M):
    t = i * (L // M) + 1
    L2.append(t)


# TMP
x = min(10**5, L)
# LS = [None] * x
# for i, li in enumerate(L1):
#     ind = li-1
#     LS[ind] = S[i]

# ans = True
# for i, li in enumerate(L2):
#     ind = li-1
#     if LS[ind] is not None:
#         if LS[ind] != T[i]:
#             ans = False

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


# print(L1)
# print(L2)
# print(LS)

Submission status: Runtime Error

Solution code:
from fractions import gcd

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

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

L1 = [1]
L2 = [1]
for i in range(1, N):
    t = i * (L // N) + 1
    L1.append(t)

for i in range(1, M):
    t = i * (L // M) + 1
    L2.append(t)


# TMP
x = min(10**5, L)
LS = [None] * x
for i, li in enumerate(L1):
    ind = li-1
    LS[ind] = S[i]

ans = True
for i, li in enumerate(L2):
    ind = li-1
    if LS[ind] is not None:
        if LS[ind] != T[i]:
            ans = False

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


# print(L1)
# print(L2)
# print(LS)

Submission status: Runtime Error

Solution code:
from fractions import gcd

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

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

L1 = [1]
L2 = [1]
for i in range(1, N):
    t = i * (L // N) + 1
    L1.append(t)

for i in range(1, M):
    t = i * (L // M) + 1
    L2.append(t)


LS = [None] * L
# for i, li in enumerate(L1):
#     ind = li-1
#     LS[ind] = S[i]

ans = True
# for i, li in enumerate(L2):
#     ind = li-1
#     if LS[ind] is not None:
#         if LS[ind] != T[i]:
#             ans = False

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


# print(L1)
# print(L2)
# print(LS)

Submission status: Runtime Error

Solution code:
from fractions import gcd

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

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

L1 = [1]
L2 = [1]
for i in range(1, N):
    t = i * (L // N) + 1
    L1.append(t)

for i in range(1, M):
    t = i * (L // M) + 1
    L2.append(t)


LS = [None] * L
# for i, li in enumerate(L1):
#     ind = li-1
#     LS[ind] = S[i]

ans = True
# for i, li in enumerate(L2):
#     ind = li-1
#     if LS[ind] is not None:
#         if LS[ind] != T[i]:
#             ans = False
############################

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


# print(L1)
# print(L2)
# print(LS)

Submission status: Runtime Error

Solution code:
from fractions import gcd

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

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

L1 = [1]
L2 = [1]
for i in range(1, N):
    t = i * (L // N) + 1
    L1.append(t)

for i in range(1, M):
    t = i * (L // M) + 1
    L2.append(t)

LS = [None] * L
for i, li in enumerate(L1):
    ind = li-1
    LS[ind] = S[i]

ans = True
# for i, li in enumerate(L2):
#     ind = li-1
#     if LS[ind] is not None:
#         if LS[ind] != T[i]:
#             ans = False

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


# print(L1)
# print(L2)
# print(LS)

Submission status: Runtime Error

Solution code:
from fractions import gcd

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

L = (N * M) // gcd(N, M)
# L = 10 ** 5 + 10

L1 = [1]
L2 = [1]
for i in range(1, N):
    t = i * (L // N) + 1
    L1.append(t)

for i in range(1, M):
    t = i * (L // M) + 1
    L2.append(t)

# LS = [None] * L
# for i, li in enumerate(L1):
#     ind = li-1
#     LS[ind] = S[i]

# ans = True
# for i, li in enumerate(L2):
#     ind = li-1
#     if LS[ind] is not None:
#         if LS[ind] != T[i]:
#             ans = False

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


# print(L1)
# print(L2)
# print(LS)

Submission status: Runtime Error

Solution code:
from fractions import gcd

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

L = (N * M) // gcd(N, M)
# L = 10 ** 5 + 10

L1 = [1]
L2 = [1]
# for i in range(1, N):
#     t = i * (L // N) + 1
#     L1.append(t)

# for i in range(1, M):
#     t = i * (L // M) + 1
#     L2.append(t)

LS = [None] * L
for i, li in enumerate(L1):
    ind = li-1
    LS[ind] = S[i]

ans = True
for i, li in enumerate(L2):
    ind = li-1
    if LS[ind] is not None:
        if LS[ind] != T[i]:
            ans = False

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


# print(L1)
# print(L2)
# print(LS)

Submission status: Runtime Error

Solution code:
from fractions import gcd

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

L = (N * M) // gcd(N, M) + (10 ** 5)
# L = int((N * M) / gcd(N, M))
# g = gcd(N, M)
# nm = N * M
# L = nm // g
# L = 10 ** 5 + 10

L1 = [1]
L2 = [1]
for i in range(1, N):
    t = i * (L // N) + 1
    L1.append(t)

for i in range(1, M):
    t = i * (L // M) + 1
    L2.append(t)

LS = [None] * L
for i, li in enumerate(L1):
    ind = li-1
    LS[ind] = S[i]

ans = True
for i, li in enumerate(L2):
    ind = li-1
    if LS[ind] is not None:
        if LS[ind] != T[i]:
            ans = False

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


# print(L1)
# print(L2)
# print(LS)

Submission status: Runtime Error

Solution code:
from fractions import gcd

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

# L = (N * M) // gcd(N, M)
# L = int((N * M) / gcd(N, M))
g = gcd(N, M)
nm = N * M
L = nm // g
# L = 10 ** 5 + 10

L1 = [1]
L2 = [1]
for i in range(1, N):
    t = i * (L // N) + 1
    L1.append(t)

for i in range(1, M):
    t = i * (L // M) + 1
    L2.append(t)

LS = [None] * L
for i, li in enumerate(L1):
    ind = li-1
    LS[ind] = S[i]

ans = True
for i, li in enumerate(L2):
    ind = li-1
    if LS[ind] is not None:
        if LS[ind] != T[i]:
            ans = False

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


# print(L1)
# print(L2)
# print(LS)

Submission status: Runtime Error

Solution code:
from fractions import gcd

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

# L = (N * M) // gcd(N, M)
# L = int((N * M) / gcd(N, M))
g = gcd(N, M)
nm = N * M
L = g // nm
# L = 10 ** 5 + 10

L1 = [1]
L2 = [1]
for i in range(1, N):
    t = i * (L // N) + 1
    L1.append(t)

for i in range(1, M):
    t = i * (L // M) + 1
    L2.append(t)

LS = [None] * L
for i, li in enumerate(L1):
    ind = li-1
    LS[ind] = S[i]

ans = True
for i, li in enumerate(L2):
    ind = li-1
    if LS[ind] is not None:
        if LS[ind] != T[i]:
            ans = False

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


# print(L1)
# print(L2)
# print(LS)

Submission status: Runtime Error

Solution code:
from fractions import gcd

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

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

L1 = [1]
L2 = [1]
for i in range(1, N):
    t = i * (L // N) + 1
    L1.append(t)

for i in range(1, M):
    t = i * (L // M) + 1
    L2.append(t)

LS = [None] * L
for i, li in enumerate(L1):
    ind = li-1
    LS[ind] = S[i]

ans = True
for i, li in enumerate(L2):
    ind = li-1
    if LS[ind] is not None:
        if LS[ind] != T[i]:
            ans = False

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


# print(L1)
# print(L2)
# print(LS)

Submission status: Runtime Error

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

from fractions import gcd
# L = (N * M) // gcd(N, M)
L = int((N * M) / gcd(N, M))

L1 = [1]
L2 = [1]
for i in range(1, N):
    t = i * (L // N) + 1
    L1.append(t)

for i in range(1, M):
    t = i * (L // M) + 1
    L2.append(t)

LS = [None] * L
for i, li in enumerate(L1):
    ind = li-1
    LS[ind] = S[i]

ans = True
for i, li in enumerate(L2):
    ind = li-1
    if LS[ind] is not None:
        if LS[ind] != T[i]:
            ans = False

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


# print(L1)
# print(L2)
# print(LS)

Submission status: Runtime Error

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

from fractions import gcd
L = (N * M) // gcd(N, M)

L1 = [1]
L2 = [1]
for i in range(1, N):
    t = i * (L // N) + 1
    L1.append(t)

for i in range(1, M):
    t = i * (L // M) + 1
    L2.append(t)

LS = [None] * L
for i, li in enumerate(L1):
    ind = li-1
    LS[ind] = S[i]

ans = True
for i, li in enumerate(L2):
    ind = li-1
    if LS[ind] is not None:
        if LS[ind] != T[i]:
            ans = False

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


# print(L1)
# print(L2)
# print(LS)