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:
n,m = map(int,input().split())
s = input()
t = input()
#greatest common divisor/least common multiple
import math
gcd = int(math.gcd(n,m))
lcm = int(n*m/gcd)
counter=0
for i in range(gcd):
    if s[1+int(m/gcd)*i]!=t[int(n/gcd)*i+1]:
        print(-1)
        counter+=1
        exit()
if counter == 0:
    print(lcm)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
s = input()
t = input()
#greatest common divisor/least common multiple
import math
gcd = math.gcd(n,m)
lcm = n*m/gcd
l = lcm/((m/gcd)(n/gcd))
counter=0
for i in range(l):
    if s[1+n/gcd]!=t[m/gcd]:
        print(-1)
        counter+=1
        exit()
if counter == 0:
    print(lcm)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
S = input()
T = input()
import math
gcd_in = (math.gcd(N,M))
lcm_in =  M*N / gcd_in
if gcd_in == 1:
    print(M*M)
elif gcd_in == M or gcd_in == N:
    for i in range(gcd_in):
        counter=0
        if S[(N//gcd_in)*i] == T[(M//gcd_in)*i]:
            counter += 1
    if counter==gcd_in:
        print(max(N,M))
    else:
        print(-1)
else:
    for i in range(int(min(lcm_in/N,lcm_in/M))):
        print(min(lcm_in/N,lcm_in/M))
        counter=0
        if S[int(lcm_in/M*i)] == T[int(lcm_in/N*i)]:
            counter += 1
        if counter==(int(min(lcm_in/N,lcm_in/M))):
            print(lcm_in)
            break
        else:
            print(-1)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
S = input()
T = input()
import math
gcd_in = (math.gcd(N,M))
lcm_in =  M*N / gcd_in
if gcd_in == 1:
    print(M*M)
elif gcd_in == M or gcd_in == N:
    for i in range(gcd_in):
        counter=0
        if S[(N//gcd_in)*i] == T[(M//gcd_in)*i]:
            counter += 1
    if counter==gcd_in:
        print(max(N,M))
    else:
        print(-1)
else:
    for i in range(min(lcm_in/N,lcm_in/M)):
        counter=0
        if S[lcm_in/M*i] == T[lcm_in/N*i]:
            counter += 1
        if counter==(min(lcm_in/N,lcm_in/M)):
            print(lcm_in)
        else:
            print(-1)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().split())
S = input()
T = input()
import math
gcd_in = (math.gcd(N,M))
print(gcd_in)
lcm_in =  M*N / gcd_in
if gcd_in == 1:
    print(M*M)
elif gcd_in == M or gcd_in == N:
    for i in range(gcd_in):
        counter=0
        if S[(N//gcd_in)*i] == T[(M//gcd_in)*i]:
            counter += 1
    if counter==gcd_in:
        print(max(N,M))
    else:
        print(-1)
else:
    for i in range(min(lcm_in/N,lcm_in/M)):
        counter=0
        if S[lcm_in/M*i] == T[lcm_in/N*i]:
            counter += 1
        if counter==(min(lcm_in/N,lcm_in/M)):
            print(lcm_in)
        else:
            print(-1)

Submission status: Runtime Error

Solution code:
N,M = map(int,input().stlip())
S = input()
T = input()
import math
gcd_in = (math.gcd(N,M))
lcm_in = (math.lcm(N,M))
if gcd_in == 1:
    print(M*M)
elif gcd_in == M or gcd_in == N:
    for i in range(gcd_in):
    counter=0
        if S[N/gcd_in*i] == T[M/gcd_in*i]:
            counter += 1
    if counter==gcd_in:
        print(max(N,M))
    else:
        print(-1)
else:
    for i in range(min(lcm_in/N,lcm_in/M)):
    counter=0
        if S[lcm_in/M*i] == T[lcm_in/N*i]:
            counter += 1
        if counter==(min(lcm_in/N,lcm_in/M)):
            print(lcm_in)
        else:
            print(-1)

Submission status: Runtime Error

Solution code:
from fractions import*
a,b=map(int,input().split())
c=a*b//gcd(a,b)
d=[0]*c
s=input()
t=input()
for i in range(a):
    d[i*(c//a)]=s[i]
for i in range(b):
    if d[i*(c//b)]!=t[i]:
        if d[i*(c//b)]==0:
            continue
        else:
            print(-1)
            exit()
print(c)

Submission status: Runtime Error

Solution code:
from fractions import*
a,b=map(int,input().split())
c=a*b//gcd(a,b)
d=[0]*c
s=input()
t=input()
for i in range(a):
    try:
        d[i*(c//a)]=s[i]
    except:
for i in range(b):
    if d[i*(c//b)]!=t[i]:
        if d[i*(c//b)]==0:
            continue
        else:
            print(-1)
            exit()
    print(-1)
print(c)

Submission status: Runtime Error

Solution code:
from fractions import*
a,b=map(int,input().split())
c=a*b//gcd(a,b)
d=[0]*c
s=input()
t=input()
for i in range(a):
    d[i*(c//a)]=s[i]
for i in range(b):
    try:
        if d[i*(c//b)]!=t[i]:
            if d[i*(c//b)]==0:
                continue
            else:
                print(-1)
                exit()
    except:
        print(-1)
print(c)

Submission status: Runtime Error

Solution code:
n,m=map(int, input().split())
s=input()
t=input()
def euc(x,y):
  if x % y==0:
    return x
  else:
    return euc(max(x,y) % min (x,y),min(x,y))
d=euc(n,m)
ans=n*int(m/d)
if d==1:
  print(n*m)
else:
  for i in range(d):
    if s[i*int(n/d)]!=t[i*int(m/d)]:
      ans=-1
  print(ans)

Submission status: Runtime Error

Solution code:
n,m=map(int, input().split())
s=input()
t=input()
def euc(x,y):
  if x % y==0:
    return x
  else:
    return euc(max(x,y) % min (x,y),min(x,y))
d=euc(n,m)
ans=int(n*m/d)
if d==1:
  print(n*m)
else:
  for i in range(d):
    if s[i*int(n/d)]!=t[i*int(m/d)]:
      ans=-1
  print(ans)

Submission status: Runtime Error

Solution code:
n,m=map(int, input().split())
s=input()
t=input()
def euc(x,y):
  if x % y==0:
    return x
  else:
    return euc(max(x,y) % min (x,y),min(x,y))
d=euc(n,m)
ans=n*m/d
if d==1:
  print(n*m)
else:
  for i in range(d):
    if s[i*int(n/d)]!=t[i*int(m/d)]:
      ans=-1
  print(ans)

Submission status: Runtime Error

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

def gcd(x,y):
  r=x%y
  return gcd(y,r) if r else y
#最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

L=lcm(n,m)
g=gcd(n,m)
if s[0]==t[0]:
  X=[""]*(L+1)
  print(X)
else:
  print(-1)
  exit()
for i in range(1,g):
  X[int(i*L/n)+1]=s[i]
for i in range(1,g):
  if X[int(i*L/m)+1] !="":
    if X[int(i*L/m)+1] !=t[i]:
      print(-1)
      exit()
print(L)

Submission status: Runtime Error

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

def gcd(x,y):
  r=x%y
  return gcd(y,r) if r else y
#最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

L=lcm(n,m)
if s[0]==t[0]:
  X=[""]*(L+1)
else:
  print(-1)
  exit()
for i in range(1,n):
  X[int(i*L/n)+1]=s[i]
for i in range(1,m):
  if X[int(i*L/m)+1] !="":
    if X[int(i*L/m)+1] !=t[i]:
      print(-1)
      exit()
print(L)

Submission status: Runtime Error

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

def gcd(x,y):
  r=x%y
  return gcd(y,r) if r else y
#最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

L=lcm(n,m)
if s[0]==t[0]:
  X=[""]*L+1
else:
  print(-1)
  exit()
for i in range(1,n):
  X[int(i*L/n)+1]=s[i]
for i in range(1,m):
  if X[int(i*L/m)+1] !="":
    if X[int(i*L/m)+1] !=t[i]:
      print(-1)
      exit()
print(L)

Submission status: Runtime Error

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

def gcd(x,y):
  r=x%y
  return gcd(y,r) if r else y
#最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

L=lcm(n,m)
if s[0]==t[0]:
  X=[""]*(10**6+1)
else:
  print(-1)
  exit()
for i in range(1,n):
  X[int(i*L/n)+1]=s[i]
for i in range(1,m):
  if X[int(i*L/m)+1] !="":
    if X[int(i*L/m)+1] !=t[i]:
      print(-1)
      exit()
print(L)

Submission status: Runtime Error

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

def gcd(x,y):
  r=x%y
  return gcd(y,r) if r else y
#最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

L=lcm(n,m)
if s[0]==t[0]:
  X=[""]*(10**5+1)
else:
  print(-1)
  exit()
for i in range(1,n):
  X[int(i*L/n)+1]=s[i]
for i in range(1,m):
  if X[int(i*L/m)+1] !="":
    if X[int(i*L/m)+1] !=t[i]:
      print(-1)
      exit()
print(L)

Submission status: Runtime Error

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

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

def gcd(x,y):
  r=x%y
  return gcd(y,r) if r else y
#最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

L=lcm(n,m)
if s[0]==t[0]:
  X=[""]*(10**5)
else:
  print(-1)
  exit()
for i in range(1,n):
  X[int(i*L/n)]=s[i]
for i in range(1,m):
  if X[int(i*L/m)] !="":
    if X[int(i*L/m)] !=t[i]:
      print(-1)
      exit()
print(L)

Submission status: Runtime Error

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

def gcd(x,y):
  r=x%y
  return gcd(y,r) if r else y
#最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

L=lcm(n,m)
if s[0]==t[0]:
  X=[""]*(L*2)
else:
  print(-1)
  exit()
for i in range(1,n):
  X[int(i*L/n)]=s[i]
for i in range(1,m):
  if X[int(i*L/m)] !="":
    if X[int(i*L/m)] !=t[i]:
      print(-1)
      exit()
print(L)

Submission status: Runtime Error

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

def gcd(x,y):
  r=x%y
  return gcd(y,r) if r else y
#最小公倍数
def lcm(x, y):
    return (x * y) // gcd(x, y)

L=lcm(n,m)
if s[0]==t[0]:
  X=[""]*L
else:
  print(-1)
  exit()
for i in range(1,n):
  X[int(i*L/n)]=s[i]
for i in range(1,m):
  if X[int(i*L/m)] !="":
    if X[int(i*L/m)] !=t[i]:
      print(-1)
      exit()
print(L)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
N, M = list(map(int, input().split()))
S = input()
T = input()
g = gcd(N,M)
r = N*M//g
for i in range(g):
  if S[N//g*i] != T[M//g*i]:
    r = -1
print(r)

Submission status: Runtime Error

Solution code:
import bisect
N,M=map(int,input().split())

X=max(N,M)
Y=min(N,M)
while X%Y!=0:
    X,Y=Y,X%Y

lcm=(N*M)//Y

#print(lcm)

s=[i*lcm//N for i in range(N)]
t=[i*lcm//M for i in range(M)]
t.append(10000000)
S=input()
T=input()

for i in range(len(s)):
    if t[bisect.bisect_left(t,s[i])]==s[i]:
        if T[bisect.bisect_left(t,s[i])]==S[i]:
            pass
        else:
            print(-1)
            exit()
print(lcm)

Submission status: Runtime Error

Solution code:
import bisect
N,M=map(int,input().split())

X=max(N,M)
Y=min(N,M)
while X%Y!=0:
    X,Y=Y,X%Y

lcm=(N*M)//Y

#print(lcm)

s=[i*lcm//N for i in range(N)]
t=[i*lcm//M for i in range(M)]
t.append(10000000)
S=input()
T=input()

for i in range(len(s)):
    if t[bisect.bisect_left(t,s[i])]==s[i]:
        if T[bisect.bisect_left(t,s[i])]==S[i]:
            pass
        else:
            print(-1)
            exit()
print(lcm)

Submission status: Runtime Error

Solution code:
import fractions

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

try:
  XS = [' ']*L
  XT = [' ']*L
except:
  L = L // 10
  XS = [' ']*L
  XT = [' ']*L

for i in range(N):
  idx = L//N*i
  try:
    XS[idx] = S[i]
  except:
    pass

for i in range(M):
  idx = L//M*i
  try:
    XT[idx] = T[i]
  except:
    pass

  if XS[i] == ' ' or XT[i] == ' ':
    continue
  elif XS[i] == XT[i]:
    continue
  else:
    print(-1)
    exit()

print(L)

Submission status: Runtime Error

Solution code:
import fractions

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

XS = [' ']*L
XT = [' ']*L

for i in range(N):
  idx = L//N*i
  try:
    XS[idx] = S[i]
  except:
    pass

for i in range(M):
  idx = L//M*i
  try:
    XT[idx] = T[i]
  except:
    pass

  if XS[i] == ' ' or XT[i] == ' ':
    continue
  elif XS[i] == XT[i]:
    continue
  else:
    print(-1)
    exit()

print(L)

Submission status: Runtime Error

Solution code:
import fractions

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

XS = [' ']*L
XT = [' ']*L

for i in range(N):
  idx = L//N*i
  XS[idx] = S[i]

for i in range(M):
  idx = L//M*i
  XT[idx] = T[i]

for i in range(L//2):
  if XS[i] == ' ' or XT[i] == ' ':
    continue
  elif XS[i] == XT[i]:
    continue
  else:
    print(-1)
    exit()

print(L)

Submission status: Runtime Error

Solution code:
import fractions

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

XS = [' ']*L
XT = [' ']*L

for i in range(N):
  idx = L//N*i
  XS[idx] = S[i]

for i in range(M):
  idx = L//M*i
  XT[idx] = T[i]

for i in range(L):
  if XS[i] == ' ' or XT[i] == ' ':
    continue
  elif XS[i] == XT[i]:
    continue
  else:
    print(-1)
    exit()

print(L)

Submission status: Runtime Error

Solution code:
import fractions

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

def S_ni_naru(X_S, S, L, N):
    for i in range(N):
        idx = L//N*i
        X_S[idx] = S[i]
    return X_S


def T_ni_naru(X_T, T, L, M):
    for i in range(M):
        idx = L//M*i
        X_T[idx] = T[i]
    return X_T

X_S = S_ni_naru([0]*L, S, L, N)
X_T = T_ni_naru([0]*L, T, L, M)

for s, t in zip(X_S, X_T):
    if (s != t) and (s != 0) and (t != 0):
        print(-1)
        exit()

print(L)

Submission status: Runtime Error

Solution code:
import fractions


def main():
    X_S = S_ni_naru([0]*L, S, L, N)
    X_T = T_ni_naru([0]*L, T, L, M)

    for s, t in zip(X_S, X_T):
        if (s != t) and (s != 0) and (t != 0):
            print(-1)
            exit()

    print(L)


def S_ni_naru(X_S, S, L, N):
    s_i = 0
    for i in range(N):
        if i == 0:
            idx = 0
        else:
            idx = min(L//N*i, len(X_S)-1)

        X_S[idx] = S[s_i]
        s_i = s_i + 1

    return X_S


def T_ni_naru(X_T, T, L, M):
    t_i = 0
    for i in range(M):
        if i == 0:
            idx = 0
        else:
            idx = min(L//M*i, len(X_T)-1)

        X_T[idx] = T[t_i]
        t_i = t_i + 1

    return X_T


if __name__ == "__main__":
    N, M = map(int, input().split())
    S = input()
    T = input()
    L = int((N*M) / fractions.gcd(N, M))
    main()

Submission status: Runtime Error

Solution code:
import fractions


def main():
    X_S = S_ni_naru([0]*(L+1), S, L, N)
    X_T = T_ni_naru([0]*(L+1), T, L, M)

    for s, t in zip(X_S, X_T):
        if (s != t) and (s != 0) and (t != 0):
            print(-1)
            exit()

    print(L)


def S_ni_naru(X_S, S, L, N):
    for i in range(N):
        idx = L//N*i
        X_S[idx] = S[i]
    return X_S


def T_ni_naru(X_T, T, L, M):
    for i in range(M):
        idx = L//M*i
        X_T[idx] = T[i]
    return X_T


if __name__ == "__main__":
    N, M = map(int, input().split())
    S = input()
    T = input()
    L = N*M//fractions.gcd(N, M)
    main()

Submission status: Runtime Error

Solution code:
import fractions


def main():
    X_S = S_ni_naru([0]*L, S, L, N)
    X_T = T_ni_naru([0]*L, T, L, M)

    for s, t in zip(X_S, X_T):
        if (s != t) and (s != 0) and (t != 0):
            print(-1)
            exit()

    print(L)


def S_ni_naru(X_S, S, L, N):
    for i in range(N):
        idx = L//N*i
        X_S[idx] = S[i]
    return X_S


def T_ni_naru(X_T, T, L, M):
    for i in range(M):
        idx = L//M*i
        X_T[idx] = T[i]
    return X_T


if __name__ == "__main__":
    N, M = map(int, input().split())
    S = input()
    T = input()
    L = N*M//fractions.gcd(N, M)
    main()

Submission status: Runtime Error

Solution code:
import fractions


def main():
    X_S = S_ni_naru([0]*L, S, L, N)
    X_T = T_ni_naru([0]*L, T, L, M)

    for s, t in zip(X_S, X_T):
        if (s != t) and (s != 0) and (t != 0):
            print(-1)
            exit()

    print(L)


def S_ni_naru(X_S, S, L, N):
    s_i = 0
    for i in range(N):
        if i == 0:
            idx = 0
        else:
            idx = L//N*i

        X_S[idx] = S[s_i]
        s_i = s_i + 1

    return X_S


def T_ni_naru(X_T, T, L, M):
    t_i = 0
    for i in range(M):
        if i == 0:
            idx = 0
        else:
            idx = L//M*i

        X_T[idx] = T[t_i]
        t_i = t_i + 1

    return X_T


if __name__ == "__main__":
    N, M = map(int, input().split())
    S = input()
    T = input()
    L = int((N*M) / fractions.gcd(N, M))
    main()

Submission status: Runtime Error

Solution code:
import fractions


def main():
    X_S = S_ni_naru([0]*L, S, L, N)
    X_T = T_ni_naru([0]*L, T, L, M)

    flag = True
    for s, t in zip(X_S, X_T):
        if (s != t) and (s != 0) and (t != 0):
            flag = False
            break

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


def S_ni_naru(X_S, S, L, N):
    s_i = 0
    for i in range(N):
        if i == 0:
            idx = 0
        else:
            idx = int((L*i)/N)

        X_S[idx] = S[s_i]
        s_i = s_i + 1

    return X_S


def T_ni_naru(X_T, T, L, M):
    t_i = 0
    for i in range(M):
        if i == 0:
            idx = 0
        else:
            idx = int((L*i)/M)

        X_T[idx] = T[t_i]
        t_i = t_i + 1

    return X_T


if __name__ == "__main__":
    N, M = map(int, input().split())
    S = input()
    T = input()
    L = int((N*M) / fractions.gcd(N, M))
    main()

Submission status: Runtime Error

Solution code:
import fractions


def main():
    X_S = S_ni_naru([0]*L, S, L, N)
    X_T = T_ni_naru([0]*L, T, L, M)

    for s, t in zip(X_S, X_T):
        if (s != t) and (s != 0) and (t != 0):
            print(-1)
            exit()

    print(L)


def S_ni_naru(X_S, S, L, N):
    s_i = 0
    for i in range(N):
        if i == 0:
            idx = 0
        else:
            idx = int((L*i)/N)

        X_S[idx] = S[s_i]
        s_i = s_i + 1

    return X_S


def T_ni_naru(X_T, T, L, M):
    t_i = 0
    for i in range(M):
        if i == 0:
            idx = 0
        else:
            idx = int((L*i)/M)

        X_T[idx] = T[t_i]
        t_i = t_i + 1

    return X_T


if __name__ == "__main__":
    N, M = map(int, input().split())
    S = input()
    T = input()
    L = int((N*M) / fractions.gcd(N, M))
    main()

Submission status: Runtime Error

Solution code:
import fractions


def main():
    N, M = map(int, input().split())
    S = input()
    T = input()
    L = int((N*M) / fractions.gcd(N, M))
    X_S = S_ni_naru([0]*L, S, L, N)
    X_T = T_ni_naru([0]*L, T, L, M)

    for s, t in zip(X_S, X_T):
        if (s != t) and (s != 0) and (t != 0):
            print(-1)
            exit()

    print(L)


def S_ni_naru(X_S, S, L, N):
    s_i = 0
    for i in range(N):
        if i == 0:
            idx = 0
        else:
            idx = int((L*i)/N)

        X_S[idx] = S[s_i]
        s_i = s_i + 1

    return X_S


def T_ni_naru(X_T, T, L, M):
    t_i = 0
    for i in range(M):
        if i == 0:
            idx = 0
        else:
            idx = int((L*i)/M)

        X_T[idx] = T[t_i]
        t_i = t_i + 1

    return X_T


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import fractions


def main():
    N, M = map(int, input().split())
    S = input()
    T = input()
    L = int((N*M) / fractions.gcd(N, M))
    X_S = S_ni_naru([0]*L, S, L, N)
    X_T = T_ni_naru([0]*L, T, L, M)

    for s, t, idx in zip(X_S, X_T, range(L)):
        if (s != t) and (s != 0) and (t != 0):
            print(-1)
            exit()

    print(L)


def S_ni_naru(X_S, S, L, N):
    s_i = 0
    for i in range(N):
        if i == 0:
            idx = 0
        else:
            idx = int((L*i)/N)

        X_S[idx] = S[s_i]
        s_i = s_i + 1

    return X_S


def T_ni_naru(X_T, T, L, M):
    t_i = 0
    for i in range(M):
        if i == 0:
            idx = 0
        else:
            idx = int((L*i)/M)

        X_T[idx] = T[t_i]
        t_i = t_i + 1

    return X_T


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import math


def main():
    N, M = map(int, input().split())
    S = input()
    T = input()
    L = int((N*M) / math.gcd(N, M))  # 最小公倍数

    if S[0] != T[0]:
        print(-1)
    else:
        print(L)  # まさかな・・・

    # これ、enumarateとかzipでX出力できない？
    # 10^5 って線形探索でギリギリいけるんだっけ…？
    # 別の頭のいい方法が分かるはず。


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import fractions as math

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

if __name__ == "__main__":
    main()

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

    nmlcm = lcm(n,m)
    nn = nmlcm // n
    mm = nmlcm // m

    for i in range(lcm(n,m)):
        if i%nn == 0 and i%mm == 0 and s[i//nn] != t[i//mm]:
            print(-1)
            return
    print(nmlcm)

Submission status: Runtime Error

Solution code:
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0, i##_len=(n); i<i##_len; ++i)
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
#define MEMSET(v, h) memset((v), h, sizeof(v))
#define pb push_back
#define mp make_pair
#define y0 y3487465
#define y1 y8687969
#define j0 j1347829
#define j1 j234892
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; }
using namespace std;

int main(){
  int N,M;
  cin >> N >> M;
  string S,T;
  cin >> S >> T;
  if(N==M){
    if(S!=T){
      cout << -1 << endl;
      return 0;
    }
    else cout << N*N << endl;
    return 0;
  }
  ll mx = 0;
  ll mn = 0;
  string& mx_s = S;
  string& mn_s = T;
  if(N>M){
    mx = N;
    mn = M;
    string& mx_s = S;
    string& mn_s = T;
  }
  else{
    mx = M;
    mn = N;
    string& mx_s = T;
    string& mn_s = S;
  }
  ll MN = M*N;
  for(int i=0;i<mn;++i){
    ll div = (i*MN/mn) / (MN/mx);
    if( (i*MN/mn) % (MN/mx) == 0 && div <= (mx-1)){
      
      if(mn_s[i]!=mx_s[div]){
          cout << -1 << endl;
          return 0;
      }
      
    }
  }
  

  cout << (MN / __gcd(N,M)) << endl;


  return 0;
}

Submission status: Runtime Error

Solution code:
import math
N,M=map(int,input().split())
S=list(input())
T=list(input())
lcm=int(N*M/math.gcd(N,M))
L_M=int(lcm/N)
L_N=int(lcm/M)
val=[]
val1=[]
end=0
for n in range(N):
    val.append(n*L_N)
print(val)
for n in range(M):
    val1.append(n*L_M)
    if n*L_M in val:
        print(S[val.index(n*L_M)],T[n])
        if S[val.index(n*L_M)]==T[n]:
            continue
        else:
            end=1
            break
print(val1)
if end==0:
    print(lcm)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
import math
N,M=map(int,input().split())
S=list(input())
T=list(input())
lcm=int(N*M/math.gcd(N,M))
L_M=int(lcm/N)
L_N=int(lcm/M)
val=[]
val1=[]
end=0
for n in range(N):
    val.append(n*L_N)
for n in range(M):
    val1.append(n*L_M)
    if (n*L_M in val):
        if S[val.index(n*L_M)]==T[n]:
            continue
        else:
            end=1
            break
if end==0:
    print(lcm)
else:
    print(-1)

Submission status: Runtime Error

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

s1 = ['*'] * lcm(n, m)
l = len(s1)

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

for j in range(m):
    if s1[(l//m) * j] != '*':
        if s1[(l//m) * j] != t[j]:
            print(-1)
            break
    if j == m - 1:
        print(l)

Submission status: Runtime Error

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

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

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

s1 = ['*'] * lcm(n, m)
l = len(s1)

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

for j in range(m):
    if s1[(l//m) * j] != '*' and s1[(l//m) * j] != t[j]:
        print(-1)
        break
    if j == m - 1:
        print(l)

Submission status: Runtime Error

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

s1 = ['*'] * lcm(n, m)
l = len(s1)

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

for j in range(m):
    if s1[(l//m) * j] != '*' and s1[(l//m) * j] != t[j]:
        print(-1)
        break
    if j == m - 1:
        print(l)

Submission status: Runtime Error

Solution code:
import math

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

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

s1 = ['*'] * lcm(n, m)
l = len(s1)

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

for j in range(m):
    if s1[(l//m) * j] != '*' and s1[(l//m) * j] != t[j]:
        print(-1)
        break
    if j == m - 1:
        print(l)

Submission status: Runtime Error

Solution code:
import math

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

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

s1 = ['*'] * lcm(n, m)
l = len(s1)

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

for j in range(m):
    if s1[(l//m) * j] != '*' and s1[(l//m) * j] != t[j]:
        print(-1)
        break
    if j == m - 1:
        print(l)

Submission status: Runtime Error

Solution code:
from fractions import gcd
N.M=(int(i) for i in input.split())
S=input()
T=input()
gcd_NM=gcd(N,M)
lcm_NM=(N*M//gcd_NM)
A=True
for i in range(gcd_NM):
  if S[(N//gcd_NM)*i]!=T[(M//gcd_NM)*i]:
    A=False 
    break
if A:
  print(lcm_NM)
else:
  print(-1)

Submission status: Runtime Error

Solution code:
import math
def prime(x):
  p = {}
  cnt = 2
  Flag = True
  while Flag:
    last = math.ceil(x ** 0.5) 
    if cnt > last:
      break
    for i in range(cnt, last + 1):
      if x % i == 0:
        x //= i
        p[i] = 1
        cnt = i + 2
        while x % i == 0:
          x //= i
          p[i] += 1
        cnt = i + 1
        break
      if i == last:
        Flag = False
  if x != 1:
    p[x] = 1
  return p

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


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

L = lcm(N, M)

x = L // N
y = L // M
for i in range(N):
  if (i * x) % y == 0:
    if S[i] != T[(i * x) // y]:
      L = -1
      break

print(L)

Submission status: Runtime Error

Solution code:
from math import gcd

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

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

p = lcm(N, M)
i = 0
z = 1
flag = 1
while flag == 1:
    if N>M:
        if N%M == 0:
            if z > 2:
                print(-1)
                exit()
    else:
        if M%N == 0:
            if z > 2:
                print(-1)
                exit()

    p *= z
    li_s = []
    li_t = []
    flag = 0
    for i in range(len(S)):
        li_s.append(int(p/N*i))

    for i in range(len(T)):
        li_t.append(int(p/M*i))
    for i in li_s:
        if i in li_t:
            if S[li_s.index(i)] != T[li_t.index(i)]:
                flag = 1
    z += 1

print(p)

Submission status: Runtime Error

Solution code:
def gcd(a,b):
    while b!=0:
        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())
L=lcm(n,m)
text=["0"]*L
judge=True
for i in range(n):
    text[i*(L//n)]=s[i]
for j in range(m):
    if text[j*(L//m)]!="0":
        if text[j*(L//m)]!=t[j]:
            judge=False
print(L) if judge else print(-1)
#print(len(text))

Submission status: Runtime Error

Solution code:
def gcd(a,b):
    while b!=0:
        a,b=b,a%b
    return a
def lcm(a,b):
    return a*b//gcd(a,b)
n,m=map(int,input().split())
max_num=max(n,m)
s=list(input())
t=list(input())
L=lcm(n,m)
text=["0"]*(L*max_num)
judge=True
for i in range(n):
    text[i*(L//n)]=s[i]
for j in range(m):
    if text[j*(L//m)]!="0" and text[j*(L//m)]!=t[j]:
        judge=False
print(L) if judge else print(-1)
#print(len(text))

Submission status: Runtime Error

Solution code:
from fractions import gcd
from bisect import bisect_left

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

L = N*M // gcd(N, M)
 
a = G//N
b = G//M
 
X = [a*i for i in range(N)]
Y = [b*j for j in range(M)]
 
for i, x in enumerate(X):
    j = bisect_left(Y, x)
    if j < M and Y[j] == x:
        if S[i] != T[j]:
            print(-1)
            break
else:
    print(L)

Submission status: Runtime Error

Solution code:
import math

def lcm(x,y):
    return (x * y) // math.gcd(x, y)
def atwo(n,m,s,t):
    l=lcm(n,m)
    a=l/n
    b=l/m
    for i in range(n):
        for j in range(m):
            if a*i==b*j:
                if s[i]==t[j]:
                    pass
                else:
                    l=-1

    return l

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

Submission status: Runtime Error

Solution code:
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 = input()
t = input()
j = 0
a = gcd(n, m)
for i, c in enumerate(s):
	if i % a == 0:
		if c != t[i // a * m]:
			j = -1
			break
if j >= 0:
	j = lcm(n, m)
print(j)

Submission status: Runtime Error

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

import sys, re
from collections import deque, defaultdict, Counter
from math import sqrt, hypot, factorial, pi, sin, cos, radians
from heapq import heappop, heappush, heapify, heappushpop
from bisect import bisect_left, bisect_right
from itertools import permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from functools import reduce, partial
from fractions import Fraction
from string import ascii_lowercase, ascii_uppercase, digits

def input(): return sys.stdin.readline().strip()
def ceil(a, b=1): return int(-(-a // b))
def round(x): return int((x*2+1) // 2)
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

def gcd(a, b):
    while b > 0:
        a, b = b, a%b
    return a
def lcm_base(x, y):
    return (x * y) // gcd(x, y)

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

lcm = lcm_base(N, M)
N_gap = lcm // N
M_gap = lcm // M
# 一方が他方の約数の時
if max(N, M) == lcm:
    for i in range(min(N, M)):
        if S[M_gap*i] != T[N_gap*i]:
            print(-1)
            exit()
# 互いに疎
elif N * M == lcm:
    # 先頭だけ気にすればいい
    if S[0] != T[0]:
        print(-1)
        exit()
else:
    for i in range(lcm//max(N, M)):
        if S[M_gap*i] != T[N_gap*i]:
            print(-1)
            exit()
print(lcm_base(N, M))