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:
import re

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

# 最大公約数
def gcd(a, b):
  while b > 0:
    a, b = b, a%b
  return a

# 最小公倍数
def lcm(a, b):
  return a*b/gcd(a, b)

L = int(lcm(N, M))

#文字列の作成
#SをもとにX
X1 = r''
n = 0
for i in range(1,int(L)):
  if i == n * (L//N) + 1:
    X1 += S[n]
    n += 1
  else:
    X1 += r'*'
#print(X1)  
#X1とTを比べる
m = 0
ans = 0
for i in range(0,int(L)):
  if i == m * (L//M) :
    #print(i,m,X1[i],T[m])
    if X1[i] == T[m] or X1[i] == "*":
      ans = 1
      m += 1
    else:
      ans = -1
      break

if ans != -1:
  print(int(L))
else:
  print(-1)

Submission status: Runtime Error

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

N = len(S)
M = len(T)

import sys
sys.setrecursionlimit(500000)


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


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


#print(gcd(N, M))
#print(maxkobai(N, M))


L = maxkobai(N, M)
ret = L
#x = ['-' for i in range(L+1)]
x = ['-'] * (L*10)

for n in range(0, N):
    x[n * (L//N) + 1] = S[n]

# print(x)

for m in range(0, M):
    idx = m * (L // M) + 1
    x_idx = x[idx]
    if x_idx != '-' and x_idx != T[m]:
        ret = -1
        break

print(ret)

Submission status: Runtime Error

Solution code:
import sys,collections,fractions;sys.setrecursionlimit(10**7)
def Is(): return [int(x) for x in sys.stdin.readline().split()]
def Ss(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

a,b = Is()
s,t = S(),S()
lcm = a * b // fractions.gcd(a, b)
x = ["."]*lcm
for i in range(a):
    x[i*lcm//a] = s[i]
for i in range(b):
    if x[i*lcm//b] == "." or x[i*lcm//b] == t[i]:
        continue
    else:
        print(-1)
        exit()
print(lcm)

Submission status: Runtime Error

Solution code:

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

if S[0] != T[0]:
    print(-1)
    sys.exit()
#lcm_NM = lcm(N, M)
lcm_NM = (N*M)//math.gcd(N, M)

loop_flg = True
i = 0
while loop_flg==True:
    i +=1
    tmp_L1 = (i-1)*lcm_NM
    tmp_L = i*lcm_NM
    
    xn_index = [0]*(N-1)
    xm_index = [0]*(M-1)  
    for n in range(1, N):
        xn_index[n-1] = n*tmp_L//N+1
    for m in range(1, M):
        xm_index[m-1] = m*tmp_L//M+1
    n_set = set(xn_index)
    m_set = set(xm_index)
    matched_list = list(n_set & m_set)
    if len(matched_list) == 0:
        break
    else:
        for k in matched_list:
            if S[(k-1)*N//tmp_L] == T[(k-1)*M//tmp_L]:
                loop_flg = False
                continue
            else:
                t_elpsd = time.time() - t_start
                if t_elpsd > 1.9: 
                    print(-1)
                    sys.exit()
                else:
                    loop_flg = True
                    break
                    
L = tmp_L
print(L)

Submission status: Runtime Error

Solution code:
import fractions
import sys

N,M=map(int,input().split())
S=input()
T=input()
S_len=len(S)
T_len=len(T)
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)

lcm_result=lcm(S_len,T_len)
S_data=[0]*lcm_result
count=0
for i in range (0,lcm_result,int(lcm_result/N)):
    S_data[i]=(S[count])
    count+=1

T_data=[0]*lcm_result
count=0
for i in range (0,lcm_result,int(lcm_result/M)):
    T_data[i]=(T[count])
    count+=1

if S_data[0]!=T_data[0]:
    print(-1)
    sys.exit()

for j in range (0,lcm_result):
    if S_data[j]!=0 and T_data[j]!=0 and S_data[j]!=T_data[j]:
        print (-1)
        sys.exit()
print(lcm_result)

Submission status: Runtime Error

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

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

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


G = int(lcm(N,M))

answer = G

temp_S =['0']*G
temp_T =['0']*G

for i in range(N):
    temp_S[i*int(G/N)] = S[i]

for j in range(M):
    temp_T[j*int(G/M)] = T[j]

for k in range(G):
    if temp_S[k] != temp_T[k] and temp_S[k] != '0' and temp_T[k] != '0':
        answer =-1

print(answer)

Submission status: Runtime Error

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

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

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

L = lcm(N, M)
LparN = L / N
LparM = L / M

listWord = [""] * L

flag = 0

for i in range(N):
  indexN = i * LparN + 1
  if indexN > L:
    listWord[int(indexN)]  += S[i]
  else:
    flag = 1
for j in range(M):
  indexM = j * LparM + 1
  if indexM > L:
    listWord[int(indexM)] += T[j]
  else:
    flag = 1
if flag == 0:
  for k in range(len(listWord)):
    check = list(listWord[k])
    if len(check) > 1:
      for check1 in range(len(check)):
        check2 = check1 + 1
        while check2 < len(check):
          if check[check1] != check[check2]:
            flag = 1
            break
          check2 += 1
        
if flag == 0:
  print(L)
else:
  print(-1)

Submission status: Runtime Error

Solution code:
from fractions import gcd
def lcm(x,y):
    return (x*y)//gcd(x,y)
n,m=map(int,input().split())
s=input()
t=input()
w=min(m,n)
l=w//gcd(m,n)
d=lcm(m,n)
p=d//n
q=d//m
h=lcm(p,q)
for i in range(0,l-1):
    g=i*h
    if s[g//p]!=t[g//q]:
        print(-1)
        break
else:
    print(d)

Submission status: Runtime Error

Solution code:
import math

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

def solve():
    gcd = math.gcd(N, M)
    for i in range(1, gcd + 1):
        if S[-int(N / gcd) * i] != T[-int(M / gcd) * i]:
            return -1
    return N * M / gcd

print(solve())

Submission status: Runtime Error

Solution code:
from flactions import gcd
def lcm(x,y):
    return (x*y)//gcd(x,y)
n,m=map(int,input().split())
s=input()
t=input()
w=min(m,n)
l=w//gcd(m,n)
d=lcm(m,n)
p=d//n
q=d//m
h=lcm(p,q)
for i in range(0,l-1):
    g=i*h
    if s[g//p]!=t[g//q]:
        print(-1)
        break
else:
    print(d)

Submission status: Runtime Error

Solution code:
import fractions
import sys

N,M=map(int,input().split())
S=input()
T=input()
S_len=len(S)
T_len=len(T)
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)

lcm_result=lcm(S_len,T_len)
S_data=[0]*lcm_result
count=0
for i in range (0,lcm_result,int(lcm_result/N)):
    S_data[i]=(S[count])
    count+=1

T_data=[0]*lcm_result
count=0
for i in range (0,lcm_result,int(lcm_result/M)):
    T_data[i]=(T[count])
    count+=1

if S_data[0]!=T_data[0]:
    print(-1)
    sys.exit()

for k in range (0,lcm_result,fractions.gcd(S_len, T_len)):
    j=k+1
    if S_data[j]!=0 and T_data[j]!=0 and S_data[j]!=T_data[j]:
        print (-1)
        sys.exit()
print(lcm_result)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
s = str(input())
t = str(input())
if n > m:
    bigg = n
    summoo = m
def get_gcd(a, b):
    if a < b:
        a, b = b, a
    if a % b == 0:
        return b
    else:
        return get_gcd(b, a % b)
def get_lcm(a, b, gcd):
    lcm = a * b // gcd
    return lcm
saisyou = get_lcm(n,m,get_gcd(n,m))
unti = max(saisyou,n,m)
ans = 0
if bigg%summoo != 0:
    for l in range(unti,100000,saisyou):
        num = 0
        for i in range(min(n,m)):
            if 1+(l/n)*i+1 == 1+(l/m)*i+1:
                if s[i] == t[i]:
                    pass
                else:
                    num += 1
                    break
        if num == 0:
            ans = l
            break
    print(ans)
else:
    print(-1)

Submission status: Runtime Error

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

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

if s[0] != t[0]:
    print(-1)
    exit()
if gcd(n,m) == 1:
    print(lcm(n,m))
    exit()

ans = lcm(n,m)
nn = ans/n
mm = ans//m
e = max(nn,mm)
for i in range(1,ans,e):
    if i % (ans//n) != 0 or i%(ans//m) != 0:
        continue
    if s[i // nn] != t[i // mm]:
        print(-1)
        exit()
print(ans)

Submission status: Runtime Error

Solution code:

import sys
import math
#import time

#t_start = time.time()


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

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

if S[0] != T[0]:
    print(-1)
    sys.exit()
lcm_NM = lcm(N, M)

loop_flg = True
i = 0
while loop_flg==True:
    i +=1
    tmp_L1 = (i-1)*lcm_NM
    tmp_L = i*lcm_NM
    
    xn_index = [0]*(N-1)
    xm_index = [0]*(M-1)  
    for n in range(1, N):
        xn_index[n-1] = n*tmp_L//N+1
    for m in range(1, M):
        xm_index[m-1] = m*tmp_L//M+1
    n_set = set(xn_index)
    m_set = set(xm_index)
    matched_list = list(n_set & m_set)
    if len(matched_list) == 0:
        break
    else:
        for k in matched_list:
            if S[(k-1)*N//tmp_L] == T[(k-1)*M//tmp_L]:
                loop_flg = False
                continue
            else:
                #t_elpsd = time.time() - t_start
                if i > 10**5: 
                    print(-1)
                    sys.exit()
                else:
                    loop_flg = True
                    break
                    
L = tmp_L
print(L)

Submission status: Runtime Error

Solution code:
N, M = map(int, raw_input().split())
S = [i for i in raw_input()]
T = [i for i in raw_input()]

data = []
for i in range(1, N*M):
    ma = max([N, M])
    mi = min([N, M])

    if i * ma % mi == 0:
        data.append(i * ma)
    if i * ma > N*M:
        break

for d in data:
    slist = [j * d / N + 1  for j in range(d)][:N]
    tlist = [j * d / M + 1  for j in range(d)][:M]

    result = []
    for j in [j for j in slist if j in tlist]:
        result.append(S[slist.index(j)] == T[tlist.index(j)])
    if all(result):
        print(d)
        exit(0)

print(-1)

Submission status: Runtime Error

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

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

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

L = lcm(N, M)
LparN = L / N
LparM = L / M

listWord = [""] * 10**5

flag = 0

for i in range(N):
  indexN = i * LparN + 1
  listWord[int(indexN)]  += S[i]
for j in range(M):
  indexM = j * LparM + 1
  listWord[int(indexM)] += T[j]

for k in range(len(listWord)):
  check = list(listWord[k])
  if len(check) > 1:
    for check1 in range(len(check)):
      check2 = check1 + 1
      while check2 < len(check):
        if check[check1] != check[check2]:
          flag = 1
          break
        check2 += 1
        
if flag == 0:
  print(L)
else:
  print(-1)

Submission status: Runtime Error

Solution code:
import sys,collections,math;sys.setrecursionlimit(10**7)
def Is(): return [int(x) for x in sys.stdin.readline().split()]
def Ss(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def S(): return input()

a,b = Is()
s,t = S(),S()
lcm = a * b // math.gcd(a, b)
x = ["."]*lcm
for i in range(a):
    x[i*lcm//a] = s[i]
for i in range(b):
    if x[i*lcm//b] == "." or x[i*lcm//b] == t[i]:
        continue
    else:
        print(-1)
        exit()
print(lcm)

Submission status: Runtime Error

Solution code:
# coding:utf-8

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

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

nl = max(n, m)
while nl < 1000:
	if nl % n or nl % m:
		nl += 1
		continue
	if not max(((n - 1) * nl / n) + 1, ((m - 1) * nl / m) + 1) <= nl:
		nl += 1
		continue

	nb = True
	nl_x = [""] * nl
	for i in range(1, n):
		nl_x[int((i * nl / n) + 1)] = s[i]
	for j in range(1, m):
		if nl_x[int((j * nl / m) + 1)] == "" or nl_x[int((j * nl / m) + 1)] == t[j]:
			nl_x[int((j * nl / m) + 1)] = t[j]
		else:
			nb = False
			break
	else:
		if nb:
			print(nl)
			exit()
	nl += 1
print(-1)

Submission status: Runtime Error

Solution code:

import sys
import math
import time

t_start = time.time()


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

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

if S[0] != T[0]:
    print(-1)
    sys.exit()
lcm_NM = lcm(N, M)

loop_flg = True
i = 0
while loop_flg==True:
    i +=1
    tmp_L1 = (i-1)*lcm_NM
    tmp_L = i*lcm_NM
    
    xn_index = [0]*(N-1)
    xm_index = [0]*(M-1)  
    for n in range(1, N):
        xn_index[n-1] = n*tmp_L//N+1
    for m in range(1, M):
        xm_index[m-1] = m*tmp_L//M+1
    n_set = set(xn_index)
    m_set = set(xm_index)
    matched_list = list(n_set & m_set)
    if len(matched_list) == 0:
        break
    else:
        for k in matched_list:
            if S[(k-1)*N//tmp_L] == T[(k-1)*M//tmp_L]:
                loop_flg = False
                continue
            else:
                t_elpsd = time.time() - t_start
                if t_elpsd > 1.9: 
                    print(-1)
                    sys.exit()
                else:
                    loop_flg = True
                    break
                    
L = tmp_L
print(L)

Submission status: Runtime Error

Solution code:

import math

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

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

def my_index(l, x, default=False):
    if x in l:
        return l.index(x)
    else:
        return default

success = False;
ans = 0
_lcm = lcm(N, M)
for k in range(1, N*M//_lcm + 1):
    ans = k * _lcm
    s = [(i * ans)//N + 1 for i in range(N)]
    t = [(i * ans)//M + 1 for i in range(M)]

    pool = s + t

    double_st = [x for x in set(pool) if pool.count(x) > 1]
    isImpossible = False

    for st in double_st:
        s_i = my_index(s, st, -1)
        t_i = my_index(t, st, -1)
        if s_i == -1 or t_i == -1:
            continue
        if S[s_i] != T[t_i]:
            isImpossible = True
            
    if not isImpossible:
        success = True
        break

if not success:
    print(-1)
else:
    print(ans)

Submission status: Runtime Error

Solution code:
import math

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

#LがM,Nの最小公倍数の場合を調べる
L = int((N*M)/math.gcd(N,M))
LdN = L/N
LdM = L/M
#L文字の文字列用
X = ['0' for i in range(L)]

#2番目の条件を満たすようにSをXにはめ込む
for i in range(N):
    X[int(LdN*i)] = S[i]

#3番目の条件についての判定
#Xの1,L/M+1...文字目がTと同じまたは0ならXは「よい文字列」
for j in range(M):
    if (X[int(LdM*j)] != T[j]) and (X[int(LdM*j)] != '0'):
        flg = False

if flg == True:
    print(L)
else:
    print('-1')

Submission status: Runtime Error

Solution code:
import math

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

# S is shorter
if N > M:
    x = N
    N = M
    M = x
    x = S
    S = T
    T = x

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

Submission status: Runtime Error

Solution code:
import sys
import math
import time

t_start = time.time()


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

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

if not(S[0], T[0]):
    print(-1)
    sys.exit()
lcm_NM = lcm(N, M)

loop_flg = True
i = 0
while loop_flg:
    i +=1
    tmp_L1 = (i-1)*lcm_NM
    tmp_L = i*lcm_NM
    
    xn_index = [0]*(N-1)
    xm_index = [0]*(M-1)  
    for n in range(1, N):
        xn_index[n-1] = n*tmp_L//N+1
    for m in range(1, M):
        xm_index[m-1] = m*tmp_L//M+1
    n_set = set(xn_index)
    m_set = set(xm_index)
    matched_list = list(n_set & m_set)
    if len(matched_list) == 0:
        break
    else:
        for k in matched_list:
            if S[(k-1)*N//tmp_L] == T[(k-1)*M//tmp_L]:
                loop_flg = False
                continue
            else:
                t_elpsd = time.time() - t_start
                if t_elpsd > 1.9: 
                    print(-1)
                    sys.exit()
                else:
                    loop_flg = True
                    break
                    
L = tmp_L
print(L)

Submission status: Runtime Error

Solution code:
#coding:utf-8
import math
def lcm(x, y):
    return (x * y) // math.gcd(x, y)
n,m = map(int,input().split())
s=input()
t=input()
lcm = lcm(n,m)
a = int(lcm/n)
b = int(lcm/m)
for i in range(math.gcd(n,m)):
    if s[i*b]==t[i*a]:
        pass
    else:
        print (-1)
        exit()
print (lcm)

Submission status: Runtime Error

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


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


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


L = lcm(N, M)
X = ['0'] * L

for n in range(N):
    X[int(L * n / N)] = S[n]


for m in range(M):
    if X[int(L * m / M)] != '0' and X[int(L * m / M)] != T[m]:
        print(-1)
        quit()
    else:
        X[int(L * m / M)] = T[m]


print(len(X))

Submission status: Runtime Error

Solution code:
import math

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

# S is shorter
if N > M:
    x = N
    N = M
    M = x
    x = S
    S = T
    T = x

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

flag = True
if M % N == 0:
    n = M // N
    for i in range(N):
        if S[i] != T[n*i]:
            flag = False
if flag:
    print(LCM)
else:
    print(-1)

Submission status: Runtime Error

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

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

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

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

X = np.zeros(L, dtype=np.str)

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

for i in range(M):
    if X[i*(L//M)] == '':
        X[i*(L//M)] = T[i]
    elif X[i*(L//M)] != T[i]:
        print('-1')
        exit()

print(L)

Submission status: Runtime Error

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

N = len(S)
M = len(T)


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


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


#print(gcd(N, M))
#print(maxkobai(N, M))


L = maxkobai(N, M)
ret = L
#x = ['-' for i in range(L+1)]
x = ['-'] * (L*10)

for n in range(0, N):
    x[n * (L//N) + 1] = S[n]

# print(x)

for m in range(0, M):
    idx = m * (L // M) + 1
    x_idx = x[idx]
    if x_idx != '-' and x_idx != T[m]:
        ret = -1
        break

print(ret)

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-
"""
Created on Sat Oct 13 20:55:15 2018

@author: Owner
"""

import sys
import math
import time

t_start = time.time()


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

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

if not(S[0], T[0]):
    print(-1)
    sys.exit()
lcm_NM = lcm(N, M)

loop_flg = True
i = 0
while loop_flg:
    i +=1
    tmp_L1 = (i-1)*lcm_NM
    tmp_L = i*lcm_NM
    
    xn_index = [0]*(N-1)
    xm_index = [0]*(M-1)  
    for n in range(1, N):
        xn_index[n-1] = n*tmp_L//N+1
    for m in range(1, M):
        xm_index[m-1] = m*tmp_L//M+1
    n_set = set(xn_index)
    m_set = set(xm_index)
    matched_list = list(n_set & m_set)
    if len(matched_list) == 0:
        break
    else:
        for k in matched_list:
            if S[(k-1)*N//tmp_L] == T[(k-1)*M//tmp_L]:
                loop_flg = False
                continue
            else:
                t_elpsd = time.time() - t_start
                if t_elpsd > 1.9: 
                    print(-1)
                    sys.exit()
                else:
                    loop_flg = True
                    break
                    
L = tmp_L
print(L)

Submission status: Runtime Error

Solution code:
import collections
import scipy.misc
import sys
import numpy as np
from operator import itemgetter
import math
import time

t_start = time.time()


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

def make_divisor_list(num):
    if num < 1:
        return []
    elif num == 1:
        return [1]
    else:
        divisor_list = []
        divisor_list.append(1)
        for i in range(2, num // 2 + 1):
            if num % i == 0:
                divisor_list.append(i)
        divisor_list.append(num)

        return divisor_list

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

if not(S[0], T[0]):
    print(-1)
    sys.exit()
lcm_NM = lcm(N, M)

loop_flg = True
i = 0
while loop_flg:
    i +=1
    tmp_L1 = (i-1)*lcm_NM
    tmp_L = i*lcm_NM
    
    xn_index = [0]*(N-1)
    xm_index = [0]*(M-1)  
    for n in range(1, N):
        xn_index[n-1] = n*tmp_L//N+1
    for m in range(1, M):
        xm_index[m-1] = m*tmp_L//M+1
    n_set = set(xn_index)
    m_set = set(xm_index)
    matched_list = list(n_set & m_set)
    if len(matched_list) == 0:
        break
    else:
        for k in matched_list:
            if S[(k-1)*N//tmp_L] == T[(k-1)*M//tmp_L]:
                loop_flg = False
                continue
            else:
                t_elpsd = time.time() - t_start
                if t_elpsd > 1.9: 
                    print(-1)
                    sys.exit()
                else:
                    loop_flg = True
                    break
                    
L = tmp_L
print(L)

Submission status: Runtime Error

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


import sys
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a


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


L = lcm(N, M)
X = ['0'] * L

for n in range(N):
    X[int(L * n / N)] = S[n]


for m in range(M):
    if X[int(L * m / M)] != '0' and X[int(L * m / M)] != T[m]:
        print(-1)
        quit()
        sys.exit()
    else:
        X[int(L * m / M)] = T[m]


print(len(X))

Submission status: Runtime Error

Solution code:
import platform
ver = platform.python_version_tuple()
if int(ver[1]) < 5:
    from fractions import gcd
else:
    from math import gcd
from sys import stdin

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

    L = lcm(N, M)
    ans = [None] * L
    for j in range(N):
        k = j * (L // N)
        if ans[k] is None or ans[k] in S[j]:
            ans[k] = S[j]
        else:
            print(-1)
            return
    for j in range(M):
        k = j * (L // M)
        if ans[k] is None or ans[k] in T[j]:
            ans[k] = T[j]
        else:
            print(-1)
            return
    print(L)

input = lambda: stdin.readline().rstrip()
lcm = lambda x, y: x * y // gcd(x, y)
main()

Submission status: Runtime Error

Solution code:
import math

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

# S is shorter
if len(S) >= len(T):
    x = S
    S = T
    T = x

LCM = len(S) * len(T) // math.gcd(len(S), len(T))

flag = True
if len(T) % len(S) == 0:
    n = len(T) // len(S)
    for i in range(n):
        if S[i] != T[n*i]:
            flag = False
if flag:
    print(LCM)
else:
    print(-1)

Submission status: Runtime Error

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

def lcm(x, y):
    def gcd(a, b):
        while b:
            a, b = b, a % b
        return a
    return (x * y) // gcd(x, y)
X = lcm(N ,M)

if S[0] != T[0]:
    print(-1)
elif X == N*M:
    print(N*M)
else:
    for i in range(1,(N*M//X)+1):
        L = X * i
        counter = L
        y = L // N
        z = L // M
        match = lcm( y, z)
        for j in range(1, (L // match) ):
            if S[j * N * match // L] != T[l = j * M * match // L]:
                counter = -1
                break
        if counter == L:
            break
    print(counter)

Submission status: Runtime Error

Solution code:
import math

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

sl, tl = map(int, input().split())
s = input()
t = input()

m = lcm(sl,tl)

mps = m // sl
mpt = m // tl

tmp = 0
width = max(mps,mpt)
ans = True

while tmp < m:
    if tmp % mps == 0 and tmp % mpt == 0:
        if s[tmp//mps] != t[tmp//mpt]:
            ans = False
            break
    tmp += width

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

Submission status: Runtime Error

Solution code:
import math
import sys

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

# S is shorter
if len(S) >= len(T):
    x = S
    S = T
    T = x

LCM = len(S) * len(T) // math.gcd(len(S), len(T))

if len(T) % len(S) == 0:
    n = len(T) // len(S)
    for i in range(n):
        if S[i] != T[n*i]:
            print(-1)
            sys.exit(0)
    print(LCM)
else:
    print(LCM)

Submission status: Runtime Error

Solution code:
import math
def main():
    N, M = map(int, input().split())
    S = input()
    T = input()
    result = N * M / math.gcd(N, M)
    cand = (result / N) * (result / M) / math.gcd(int((result / N)), int((result / M)))
    for i in range(0, int(result / cand)):
        if S[int((i * cand) / (result / N))] != T[int((i * cand) / (result / M))]:
            return '-1'
    return int(result)
print(main())

Submission status: Runtime Error

Solution code:
import math

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

sl, tl = map(int, input().split())
s = input()
t = input()

# 最小公倍数
m = lcm(sl,tl)

# sとtの幅
mps = m // sl
mpt = m // tl

tmp = 0
width = max(mps,mpt)
ans = True

while tmp < m:
    if tmp % mps == 0 and tmp % mpt == 0:
        if s[tmp//mps] != t[tmp//mpt]:
            ans = False
            break
    tmp += width

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

Submission status: Runtime Error

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

flag = True
for n in range(N):
    if (M*n)%N==0:
        m = (M*n)//N
        flag = m<M
        if flag:
            flag = S[n]==T[m]
        if not flag:
            break

if flag:
    print(N*M//math.gcd(N,M))
else:
    print(-1)

Submission status: Runtime Error

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

N = len(S)
M = len(T)


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


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


#print(gcd(N, M))
#print(maxkobai(N, M))


L = maxkobai(N, M)
ret = L
#x = ['-' for i in range(L+1)]
x = ['-'] * (L+1)

for n in range(0, N):
    x[n * (L//N) + 1] = S[n]

# print(x)

for m in range(0, M):
    idx = m * (L // M) + 1
    x_idx = x[idx]
    if x_idx != '-' and x_idx != T[m]:
        ret = -1
        break

print(ret)

Submission status: Runtime Error

Solution code:

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

flag = True
for n in range(N):
    if (M*n)%N==0:
        m = (M*n)//N
        flag = m<M
        flag = S[n]==T[m]
        if not flag:
            break

if flag:
    print(N*M//math.gcd(N,M))
else:
    print(-1)

Submission status: Runtime Error

Solution code:
import math
def main():
    N, M = map(int, input().split())
    S = input()
    T = input()
    result = N * M / math.gcd(N, M)
    cand = (result / N) * (result / M) / math.gcd(int((result / N)), int((result / M)))
    for i in range(0, int(result / cand)):
        if S[int((i * cand) / (result / N))] != T[int((i * cand) / (result / M))]:
            return -1
    return int(result)
print(main())

Submission status: Runtime Error

Solution code:
import math
import numpy as np
N,M = map(int,input().split())
S = input()
T = input()

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

X = np.zeros(L, dtype=np.str)

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

for i in range(M):
    if X[i*(L//M)] == '':
        X[i*(L//M)] = T[i]
    elif X[i*(L//M)] != T[i]:
        print('-1')
        exit()

print(L)

Submission status: Runtime Error

Solution code:
import math

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

if N==M:
    print(int(N*M)) if S==T else print(-1)
else:
    g = math.gcd(N, M)
    if g==1:
        print(int(N*M))
    else:
        flag = False
        s, t = N//g, M//g
        ss = list(map(lambda x: int(x*s), list(range(0,g))))
        tt = list(map(lambda x: int(x*t), list(range(0,g))))
        for i,j in zip(ss,tt):
            if S[i]!=T[j]:
                flag = True
        if flag:
            print(-1)
        else:
            print(int(s*t*g))

Submission status: Runtime Error

Solution code:
import fractions
nm=raw_input()
nm=nm.split()
n=eval(nm[0])
m=eval(nm[1])
s=raw_input()
t=raw_input()

gg=fractions.gcd(n,m)
ll=n*m/gg
aa=ll/n
bb=ll/m
result = ll
for i in range(ll) :
    if not (i % aa):
        tmp1=i/aa
        if not(i % bb) :
            tmp2=i/bb
            if s[tmp1] != t[tmp2] :
                result= -1
print result

Submission status: Runtime Error

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

import sys
import itertools
import math

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

if N < M:
    t = M
    M = N
    N = t
    q = S
    S = T
    T = q

d = math.gcd(N, M)

n = N / d

ret = -1
for step in range(1, M+1):
    slen = step * N
    if slen % M != 0:
        continue
    mstep = slen // M
    good = True
    for i in range(N):
        u = (step * i) % mstep
        if u != 0:
            continue
        j = (step * i) // mstep
        if S[i] != T[j]:
            good = False
            break
    if good:
        ret = step * N
        break

# 出力
print("{}".format(ret))

Submission status: Runtime Error

Solution code:
import math

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

if N==M:
    print(int(N*M)) if S==T else print(-1)
else:
    g = math.gcd(N, M)
    if g==1:
        print(int(N*M))
    else:
        flag = False
        s, t = N/g, M/g
        ss = list(map(lambda x: int(x*s), list(range(0,g))))
        tt = list(map(lambda x: int(x*t), list(range(0,g))))
        for i,j in zip(ss,tt):
            if S[i]!=T[j]:
                flag = True
        if flag:
            print(-1)
        else:
            print(int(s*t*g))