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 math

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

Slist=list(S)
Tlist=list(T)

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

A=int(N/G)
B=int(M/G)

for i in range(G):
    if Slist[i*A]!=Tlist[i*B]:
        ans=-1
        break
    else:
        ans=L
print(ans)

Submission status: Runtime Error

Solution code:

NM = input()
S = input()
T = input()

listed_NM = list(map(int, NM.split()))
N = listed_NM[0]
M = listed_NM[1]
listed_S = list(S)
listed_T = list(T)
lcm = int(N*M/math.gcd(N,M))

list_S = [i*lcm/N+1 for i in range(N)]
list_T = [i*lcm/M+1 for i in range(M)]

set_S = {i*lcm/N+1 for i in range(N)}
set_T = {i*lcm/M+1 for i in range(M)}


inter = set_S.intersection(set_T)
for j,i in enumerate(inter):
    index_S = list_S.index(i)
    index_T = list_T.index(i)
    if listed_S[index_S] != listed_T[index_T]:
        print(-1)
        break
    elif j+1==len(inter):
    #else:
        print(lcm)

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 = []

flag = 0
checkIndex = 0

for i in range(N):
  indexN = i * LparN + 1
  if indexN < L:
    listWord.append([int(indexN), S[i]])
  else:
    flag = 1
for j in range(M):
  indexM = j * LparM + 1
  if indexM < L:
    endFlag = 0
    while endFlag == 0:
      if listWord[checkIndex][0] == int(indexM):
        if listWord[checkIndex][1] != T[j]:
          flag = 1
          break
        else:
          checkIndex += 1
          endFlag = 1
      else:
        if listWord[checkIndex][0] < int(indexM):
          checkIndex += 1
        else:
          endFlag = 1
        
  else:
    flag = 1
        
if flag == 0:
  print(L)
else:
  print(-1)

Submission status: Runtime Error

Solution code:
import math

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

array = list(map(int, input().strip().split(' ')))


N =  array[0]

M =  array[1]

if N < 1:
    sys.exit()

if N > 10^5:
    sys.exit()


if M < 1:
    sys.exit()

if M > 10^5:
    sys.exit()

S = str(input())

if S.islower():
	z = 0
else:
        sys.exit()


T = str(input())

if T.islower():
	z = 0
else:
        sys.exit()


chars_S = list(S)

chars_T = list(T)

a = lcm(N, M)


limit = N

if N < M:
    limit = N
    
elif N > M:
        limit = M
    
flg = a

#print(limit)

for i in range(limit-1):
    
    #print("test")
    #print(chars_T[i])

    if i==0:
        b = 0
        c = 0
    else:
            b = int(i + a / N)-1
            c = int(i + a / M)-1

    #print(b)
    #print(c)

    
    if chars_S[b]!=chars_T[c]:
            flg = -1

print(flg)

Submission status: Runtime Error

Solution code:
import numpy as np

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

# 最大公約数を求める関数
def gcd(a,b):
    rem = a % b
    while rem != 0:
        a = b
        b = rem
        rem = a % b
    return b

# 最小公倍数を求める関数
def lcm(a,b):
    return (a*b)/gcd(a,b)

# 最初の文字が異なれば -1 
if s[0] != t[0]:
    print(-1)
elif s == t:
    print(len(s))
else:
    # check variable
    # check = True
    # iter = 1
    LeastCommonMultiple  = lcm(n,m)
    # l は n,m によって割り切れて正数商を持たなければならない
    # よってnとmの公倍数でなければいけない
    # while check:
    l = int(LeastCommonMultiple*iter)
    nOl = l // n
    mOl = l // m
    # sinX = np.array([i * nOl + 1 for i in range(n)])
    # tinX = np.array([i * mOl + 1 for i in range(m)])
    sinX = [i * nOl + 1 for i in range(n)]
    tinX = [i * mOl + 1 for i in range(m)]
    matchList = list(set(sinX) & set(tinX))
    
    # if len(matchList) == 0:
    #     continue

    # scX = [np.where(sinX == commonIndex)[0][0] for commonIndex in matchList]
    # tcX = [np.where(tinX == commonIndex)[0][0] for commonIndex in matchList]

    scX = [sinX.index(commonIndex) for commonIndex in matchList]
    tcX = [tinX.index(commonIndex) for commonIndex in matchList]

    # import ipdb; ipdb.set_trace()

    if [s[sMatch] for sMatch in scX] == [t[tMatch] for tMatch in tcX]:
        # check = False
        # matchFlag = True
        print(l)
    else:
        # check = False # here
        # matchFlag = False
        print(-1)
    
    # if iter == min(len(s), len(t)):
    #     check = False
    #     matchFlag = False

    # iter += 1

    # if matchFlag:
    #     print(l)
    # else:
    #     print(-1)

Submission status: Runtime Error

Solution code:
import math

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

Slist=list(S)
Tlist=list(T)

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

A=int(N/G)
B=int(M/G)

for i in range(G):
    if Slist[i*A]!=Tlist[i*B]:
        ans=-1
        break
    else:
        ans=L
print(ans)

Submission status: Runtime Error

Solution code:

NM = input()
S = input()
T = input()

listed_NM = list(map(int, NM.split()))
N = listed_NM[0]
M = listed_NM[1]
listed_S = list(S)
listed_T = list(T)
lcm = int(N*M/math.gcd(N,M))

list_S = [i*lcm/N+1 for i in range(N)]
list_T = [i*lcm/M+1 for i in range(M)]

set_S = {i*lcm/N+1 for i in range(N)}
set_T = {i*lcm/M+1 for i in range(M)}


inter = set_S.intersection(set_T)
for j,i in enumerate(inter):
    index_S = list_S.index(i)
    index_T = list_T.index(i)
    if listed_S[index_S] != listed_T[index_T]:
        print(-1)
        break
    elif j==len(inter):
        print(lcm)

Submission status: Runtime Error

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

Submission status: Runtime Error

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

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

c = ['']*l
d = ['']*l

c[0] = s[0]
a = [0]
for i in range(1,n):
    c[i*(l//n)] = s[i]
    a.append(i*(l//n))

d[0] = t[0]
b = [0]
for i in range(1,m):
    d[i*(l//m)] = t[i]
    b.append(i*(l//m))

ans = l

e = set(a + b)

for i in e:
    if l ==n or l ==m:
        ans = -1
        break
    elif c[i] == '' or d[i] == '':
        1
    elif c[i] == d[i]:
        1
    else:
        ans = -1
        break

print(ans)

Submission status: Runtime Error

Solution code:
# coding:utf-8
import sys
import os
import fractions

n, m = list(map(int, input().split()))
s = input()
t = input()
ans_str = ""
count_n = 1
count_m = 1

l = (n * m) // fractions.gcd (n, m)
ans_str_list = [""]*l 

if(s[0] == t[0]):
    ans_str_list[0] = s[0]
for i in range(l-1):
    if i+1 == count_n*(l/n)+1:
        ans_str_list[i+1] = s[count_n]
        count_n += 1
    if i+1 == count_m*(l/m)+1:
        ans_str_list[i+1] = t[count_m]
        count_m += 1
        
for j in range(l):
    if ans_str_list[j] == "":
        ans_str_list[j] = " "
    ans_str += ans_str_list[j]
ans = len(ans_str_list)

count_n = 1
count_m = 1
if(s[0] != t[0]):
    ans = -1
else:
    for k in range(l-1):
        if(k+1 <= len(s)):
            if k+1 == count_n*(l/n)+1:
                if(ans_str[k+1] != s[count_n]):
                    ans = -1
                    break
                count_n += 1
        if(k+1 <= len(t)):
            if k+1 == count_m*(l/m)+1:
                if(ans_str[k+1] != t[count_m]):
                    ans = -1
                    break
                count_m += 1
print("{}".format(ans))

Submission status: Runtime Error

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

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

d = gcd(N, M)
n = N // d
m = M // d
f = True

for i in range(1, d):
    if S[n*i] != T[m*i]:
        f = false
        break

print(N * M // d if f else -1)

Submission status: Runtime Error

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

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

c = ['']*l
d = ['']*l

c[0] = s[0]
a = [0]
for i in range(1,n):
    c[i*(l//n)] = s[i]
    a.append(i*(l//n))

d[0] = t[0]
b = [0]
for i in range(1,m):
    d[i*(l//m)] = t[i]
    b.append(i*(l//m))

ans = l

e = set(a + b)

for i in e:
    if l ==n or l ==m:
        ans = -1
        break
    elif c[i] == '' or d[i] == '':
        continue
    elif c[i] == d[i]:
        continue
    else:
        ans = -1
        break

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_L = i*lcm_NM
    
    xn_index = [0]*(N-1)
    xm_index = [0]*(M-1)  
    for n in range(N-1):
        xn_index[n] = (n+1)*tmp_L//N+1
    for m in range(M-1):
        xm_index[m] = (m+1)*tmp_L//M+1
    n_set = set(xn_index)
    m_set = set(xm_index)
    matched_list = list(n_set.intersection(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:
def gcd(a, b):
    if a < b:
        a, b = b, a
    if b == 0:
        return int(a)
    r = a % b
    return gcd(b, r)

def lcm(a,b):
  return int(a*b/gcd(a,b))
 
N,M = map(int,input().split())
S = input()
T = input()
L = lcm(N,M)
flag = True
min_len = min(Na,M)
s_index = int(int(L/M)/gcd(int(L/M),int(L/N)))
t_index = int(int(L/N)/gcd(int(L/M),int(L/N)))

if N == M:
  for i in range(N):
    if S[i] == T[i]:
      continue
    else:
      flag = False
      break
else:
  for i in range(min_len):
    if i * s_index < N-1 and i*t_index < M - 1:
      if S[i*s_index] == T[i*t_index]:
        continue
      else:
        flag = False
        break
    else:
      break
    
if flag:  
  print(L)
else:
  print(-1)

Submission status: Runtime Error

Solution code:
# coding:utf-8
import sys
import os
import fractions
f = open('A_input.txt', 'r')
sys.stdin = f

n, m = list(map(int, input().split()))
s = input()
t = input()
ans_str = ""
count_n = 1
count_m = 1

l = (n * m) // fractions.gcd (n, m)
ans_str_list = [""]*l 

if(s[0] == t[0]):
    ans_str_list[0] = s[0]
for i in range(l-1):
    if i+1 == count_n*(l/n)+1:
        ans_str_list[i+1] = s[count_n]
        count_n += 1
    if i+1 == count_m*(l/m)+1:
        ans_str_list[i+1] = t[count_m]
        count_m += 1
        
for j in range(l):
    if ans_str_list[j] == "":
        ans_str_list[j] = " "
    ans_str += ans_str_list[j]
ans = len(ans_str_list)

count_n = 1
count_m = 1
if(s[0] != t[0]):
    ans = -1
else:
    for k in range(l-1):
        if(k+1 <= len(s)):
            if k+1 == count_n*(l/n)+1:
                if(ans_str[k+1] != s[count_n]):
                    ans = -1
                    break
                count_n += 1
        if(k+1 <= len(t)):
            if k+1 == count_m*(l/m)+1:
                if(ans_str[k+1] != t[count_m]):
                    ans = -1
                    break
                count_m += 1
print("{}".format(ans))

Submission status: Runtime Error

Solution code:
NM = input()
S = input()
T = input()

listed_NM = list(map(int, NM.split()))
N = listed_NM[0]
M = listed_NM[1]
listed_S = list(S)
listed_T = list(T)
lcm = int(N*M/math.gcd(N,M))

list_S = [i*lcm/N+1 for i in range(N)]
list_T = [i*lcm/M+1 for i in range(M)]

set_S = {i*lcm/N+1 for i in range(N)}
set_T = {i*lcm/M+1 for i in range(M)}


inter = set_S.intersection(set_T)
for j,i in enumerate(inter):
    index_S = list_S.index(i)
    index_T = list_T.index(i)
    if listed_S[index_S] != listed_T[index_T]:
        print(-1)
        break
    elif j==len(inter):
        print(lcm)
        pass

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(N-1):
        xn_index[n] = (n+1)*tmp_L//N+1
    for m in range(M-1):
        xm_index[m] = (m+1)\*tmp_L//M+1
    n_set = set(xn_index)
    m_set = set(xm_index)
    matched_list = list(n_set.intersection(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:
from fractions import gcd
n, m = map(int, input().split())
s = input()
t = input()
l = n * m // gcd(n, m)
a = [""]*l
for i in range(n):
    a[i*l//n] = s[i]
for i in range(m):
    if a[i*l//m] != "":
        if a[i*l//m] == t[i]:
            continue
        else:
            print(-1)
            exit()
    else:
        continue
print(l)

Submission status: Runtime Error

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

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

c = ['']*l
d = ['']*l

c[0] = s[0]
a = [0]
for i in range(1,n):
    c[i*(l//n)] = s[i]
    a.append(i*(l//n))

d[0] = t[0]
b = [0]
for i in range(1,m):
    d[i*(l//m)] = t[i]
    b.append(i*(l//m))
ans = -1

e = set(a + b)

for i in e:
    if l ==n or l ==m:
        ans = -1
        break
    elif c[i] == '' or d[i] == '':
        ans = l
        continue
    elif c[i] == d[i]:
        ans = l
        continue
    else:
        ans = -1
        break

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(N):
        if n == 0:
            pass
        else:
            xn_index[n] = n*tmp_L//N+1
    for m in range(M):
        if m == 0:
            pass
        else:
            xm_index[m] = m*tmp_L//M+1
    n_set = set(xn_index)
    m_set = set(xm_index)
    matched_list = list(n_set.intersection(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 = map(int,input().split())
S=input()
T=input()

Slist=list(S)
Tlist=list(T)

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

A=int(N/G)
B=int(M/G)

for i in range(G):
    if Slist[i*A+1]==Tlist[i*B+1]:
        print(-1)
        break
        
print(L)

Submission status: Runtime Error

Solution code:
from fractions import gcd
n, m = map(int, input().split())
s = input()
t = input()
l = n * m // gcd(n, m)
a = [""] * (l+1)
for i in range(n):
    a[i*l//n] = s[i]
for i in range(m):
    if a[i*l//m] != "":
        if a[i*l//m] == t[i]:
            continue
        else:
            print(-1)
            exit()
    else:
        continue
print(a)
print(l)

Submission status: Runtime Error

Solution code:
nsky = n
msky = m
while not nsky % msky == 0:
    tmp = msky
    msky = nsky % msky
    nsky = tmp
skys = msky

idx_n = 1
idx_m = 1
idx_x = 0
okans = -1
skbs = 0

while n * idx_n < 10000000000 and m * idx_m < 10000000000 and okans < 0:
    if n * idx_n == m * idx_m:
        idx_2 = 0
        
        while (n/skys)*idx_2 < n:
            if s[int(n/skys)*idx_2] == t[int(m/skys)*idx_2]:
                if (n/skys)*(idx_2+1) == n:
                    okans = n * idx_n
                idx_2 = idx_2 + 1
            else:
                idx_2 = n
                
        if skbs == 0:
            skbs = idx_n

        idx_x = idx_x + 1
        idx_m = skbs * idx_x
        idx_n = skbs * idx_x
    elif n * idx_n > m * idx_m:
        idx_m = idx_m + 1
    elif n * idx_n < m * idx_m:
        idx_n = idx_n + 1

print(okans)

Submission status: Runtime Error

Solution code:
from fractions import *

def lcm(a,b): 
    return int(abs(a * b) / gcd(a,b) if a and b else 0)

def getDivisors(a,b):
    divisors = []
    for i in range(2,min(a,b)+1):
        if a % i == 0 and b % i == 0:
            divisors.append(i)
    return divisors

N,M = map(int,input().split())
a = input()
b = input()

if a[0] != b[0]:
    print(-1)
elif gcd(N,M) == 1:
    print(lcm(N,M))
elif N != M:
    divisors = getDivisors(N,M)

    for i in divisors:
        k = N//i
        l = M//i
        while k <= N and l <= M:
            if a[k] != b[l]:
                print(-1)
                quit()
            k *= 2
            l *= 2
    print(lcm(N,M))
else:
    if a == b: print(N)
    else: print(-1)

Submission status: Runtime Error

Solution code:
import math

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

cnt = 1
ns = 1
nt = 1
ss = 0
tt = 0
fail = False

ll = (n * m) // math.gcd(x, y)
l = ll

while l <= n * m:
    fail = False
    while not( ns >= l or nt >= l):
        while not(ns <= nt):
            nt += l / m 
            tt += 1

        if(ns == nt) and (s[ss] != t[tt]):
            fail = True
            break

        ns += l / n
        ss += 1
    if not(fail): 
        break
    cnt += 1
    l = ll * cnt

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

Submission status: Runtime Error

Solution code:
# coding:utf-8
import sys
import os
import fractions

n, m = list(map(int, input().split()))
s = input()
t = input()
ans_str = ""
count_n = 1
count_m = 1

l = (n * m) // fractions.gcd (n, m)
ans_str_list = [""]*l 

if(s[0] == t[0]):
    ans_str_list[0] = s[0]
for i in range(l-1):
    if i+1 == count_n*(l/n)+1:
        ans_str_list[i+1] = s[count_n]
        count_n += 1
    if i+1 == count_m*(l/m)+1:
        ans_str_list[i+1] = t[count_m]
        count_m += 1
        
for j in range(l):
    if ans_str_list[j] == "":
        ans_str_list[j] = " "
    ans_str += ans_str_list[j]
ans = len(ans_str_list)

count_n = 1
count_m = 1
for k in range(l-1):
    if(k+1 <= len(s)):
        if k+1 == count_n*(l/n)+1:
            if(ans_str[k+1] != s[count_n]):
                ans = -1
                break
            count_n += 1
    if(k+1 <= len(t)):
        if k+1 == count_m*(l/m)+1:
            if(ans_str[k+1] != t[count_m]):
                ans = -1
                break
            count_m += 1
print("{}".format(ans))

Submission status: Runtime Error

Solution code:
import functools, fraction

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

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

def check(L, NM):
    res = []
    for i in range(NM):
        res.append(int(i*(L/NM)+1))
    return res

def check2(x, L, NM):
    return int((x-1)*NM/L)

L = lcm(N,M)
ans = L


a = list(set(check(L, N)) & set(check(L, M)))
for i in a:
    if S[check2(i, L, N)] != T[check2(i, L, M)]:
        ans = -1
        break
print(ans)

Submission status: Runtime Error

Solution code:
n,m = map(int,input().split())
s = str(input())
t = str(input())
a = 0
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))
ans = 0
if saisyou == n or saisyou == m:
    print(-1)
else:
    for l in range(saisyou,100000,saisyou):
        num = 0
        xlis = []
        ylis = []
        for i in range(min(n,m)):
            xlis.append(1+(l/n)*i+1)
            ylis.append(1+(l/m)*i+1)
        yset = set(ylis)
        xset = set(xlis)
        for i in yset:
            hanntei = 0
            for j in xset:
                if i == j:
                    if s[j-1] == t[i-1]:
                        break
                    else:
                        hanntei += 1
                        break
            if hanntei >= 1:
                break
        num += 1
        ans = l
        break 
    if num == 1:
        print(ans)    
    else:
        print(-1)

Submission status: Runtime Error

Solution code:
from fractions import gcd
n, m = map(int, input().split())
s = input()
t = input()
l = n * m // gcd(n, m)
a = [""] * (n*m)
for i in range(n):
    a[i*l//n] = s[i]
for i in range(m):
    if a[i*l//m] == "" or a[i*l//m] == t[i]:
        a[i*l//m] = t[i]
    else:
        print(-1)
        exit()
print(l)

Submission status: Runtime Error

Solution code:
import functools, math

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

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

def check(L, NM):
    res = []
    for i in range(NM):
        res.append(int(i*(L/NM)+1))
    return res

def check2(x, L, NM):
    return int((x-1)*NM/L)

L = lcm(N,M)
ans = L


a = list(set(check(L, N)) & set(check(L, M)))
for i in a:
    if S[check2(i, L, N)] != T[check2(i, L, M)]:
        ans = -1
        break
print(ans)

Submission status: Runtime Error

Solution code:
input_lines = input().split()
N = int(input_lines[0])
M = int(input_lines[1])
S = input()
T = input()

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))
x = 1
count = 0
if N >= M:
    big = N
    small = M
else:
    big = M
    small = N
    
while True:
    k = L*x
    flag = 1
    for j in range(small):
        left = 0
        right = big - 1
        while left <= right:
            mid = (left+right)//2
            if((mid-1)*k/big+1 == (j-1)*k/small+1):
                if(S[mid-1] != T[j-1]):
                    flag = 0
                    count += 1
                    break
                else:
                    break
            elif((mid-1)*k/big+1 > (j-1)*k/small+1):
                right = mid - 1
            else:
                left = mid + 1
    if(flag == 1):
        print(k)
        break
    if(count == 2):
        print(-1)
        break
    x += 1

Submission status: Runtime Error

Solution code:
from fractions import gcd
n, m = map(int, input().split())
s = input()
t = input()
l = n * m // gcd(n, m)
a = [""] * (n*m)
for i in range(n):
    a[i*l//n] = s[i]
for i in range(m):
    if a[i*l//m] == "" or a[i*l//m] == t[i]:
        a[i*l//m] == t[i]
    else:
        print(-1)
        exit()
print(l)

Submission status: Runtime Error

Solution code:
import math

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

cnt = 1
ns = 1
nt = 1
ss = 0
tt = 0
fail = False

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

ll = lcm(n,m)
l = ll

while l <= n * m:
    fail = False
    while not( ns >= l or nt >= l):
        while not(ns <= nt):
            nt += l / m 
            tt += 1

        if(ns == nt) and (s[ss] != t[tt]):
            fail = True
            break

        ns += l / n
        ss += 1
    if not(fail): 
        break
    cnt += 1
    l = ll * cnt

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

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 int(N * M / gcd)
 
print(solve())

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
# coding:utf-8
import sys
import os
import math

n, m = list(map(int, input().split()))
s = input()
t = input()
ans_str = ""
count_n = 1
count_m = 1

l = (n * m) // math.gcd (n, m)
ans_str_list = [""]*l 

if(s[0] == t[0]):
    ans_str_list[0] = s[0]
for i in range(l-1):
    if i+1 == count_n*(l/n)+1:
        ans_str_list[i+1] = s[count_n]
        count_n += 1
    if i+1 == count_m*(l/m)+1:
        ans_str_list[i+1] = t[count_m]
        count_m += 1
        
for j in range(l):
    if ans_str_list[j] == "":
        ans_str_list[j] = " "
    ans_str += ans_str_list[j]
ans = len(ans_str_list)

count_n = 1
count_m = 1
for k in range(l-1):
    if(k+1 <= len(s)):
        if k+1 == count_n*(l/n)+1:
            if(ans_str[k+1] != s[count_n]):
                ans = -1
                break
            count_n += 1
    if(k+1 <= len(t)):
        if k+1 == count_m*(l/m)+1:
            if(ans_str[k+1] != t[count_m]):
                ans = -1
                break
            count_m += 1
print("{}".format(ans))

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import math


def pdbg(label, val):
    # print("[%s]%s" % (label, val))
    return


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


pNM = N / M
pMN = M / N


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


def is_unique(seq):
    return len(seq) == len(set(seq))


L = lcm(N, M)

LN = int(L / N)
LM = int(L / M)

pdbg('L', L)
pdbg('N', N)
pdbg('M', M)
pdbg('LN', LN)
pdbg('LM', LM)


LNs = []
for i in range(0, N, LN):
    LNs.append(i)
pdbg('LNs', LNs)
LMs = []
for j in range(0, M, LM):
    LMs.append(j)
pdbg('LMs', LMs)
Dpl = (set(LNs) & set(LMs))
pdbg('Dpl', Dpl)


def calculate():
    if pNM == round(pNM) or pMN == round(pMN):
        return -1
    if S[0] != T[0]:
        return -1
    for k in Dpl:
        pdbg('k', k)
        pdbg('Sk', S[k])
        pdbg('Tk', T[k])
        if S[k] != T[k]:
            return -1
    return L


print(calculate())

Submission status: Runtime Error

Solution code:
# coding:utf-8
import sys
import os
import math

n, m = map(int, input().split())
s = input()
t = input()
ans_str = ""
count_n = 1
count_m = 1

l = (n * m) // math.gcd (n, m)
ans_str_list = [""]*l 

if(s[0] == t[0]):
    ans_str_list[0] = s[0]
for i in range(l-1):
    #print("i+1 is : {}".format(i+1))
    #print("count_n*(l/n)+1 is : {}".format(count_n*(l/n)+1))
    if i+1 == count_n*(l/n)+1:
        ans_str_list[i+1] = s[count_n]
        count_n += 1
    if i+1 == count_m*(l/m)+1:
        ans_str_list[i+1] = t[count_m]
        count_m += 1
        #print("m done")
        
for j in range(l):
    if ans_str_list[j] == "":
        ans_str_list[j] = " "
    ans_str += ans_str_list[j]
ans = len(ans_str_list)

count_n = 1
count_m = 1
for k in range(l-1):
    if(k+1 <= len(s)):
        if k+1 == count_n*(l/n)+1:
            if(ans_str[k+1] != s[count_n]):
                ans = -1
                break
            count_n += 1
    if(k+1 <= len(t)):
        if k+1 == count_m*(l/m)+1:
            if(ans_str[k+1] != t[count_m]):
                #print("check m")
                ans = -1
                break
            count_m += 1
print("{}".format(ans))

Submission status: Runtime Error

Solution code:
input_lines = input().split()
N = int(input_lines[0])
M = int(input_lines[1])
S = input()
T = input()

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))
x = 1
count = 0
if N >= M:
    big = N
    small = M
else:
    big = M
    small = N
    
while True:
    k = L*x
    flag = 1
    for j in range(small):
        left = 0
        right = big - 1
        while left <= right:
            mid = (left+right)/2
            if((mid-1)*k/big+1 == (j-1)*k/small+1):
                if(S[mid-1] != T[j-1]):
                    flag = 0
                    count += 1
                    break
                else:
                    break
            elif((mid-1)*k/big+1 > (j-1)*k/small+1):
                right = mid - 1
            else:
                left = mid + 1
    if(flag == 1):
        print(k)
        break
    if(count == 2):
        print(-1)
        break
    x += 1

Submission status: Runtime Error

Solution code:
# coding:utf-8
import sys
import math

n, m = map(int, input().split())
s = input()
t = input()
ans_str = ""
count_n = 1
count_m = 1

l = (n * m) // math.gcd (n, m)
ans_str_list = [""]*l 

if(s[0] == t[0]):
    ans_str_list[0] = s[0]

for i in range(l-1):
    if i+1 == count_n*(l/n)+1:
        ans_str_list[i+1] = s[count_n]
        count_n += 1
        #print("n done")
    if i+1 == count_m*(l/m)+1:
        ans_str_list[i+1] = t[count_m]
        count_m += 1
        #print("m done")
        
for j in range(l):
    if ans_str_list[j] == "":
        ans_str_list[j] = " "
    ans_str += ans_str_list[j]
ans = len(ans_str_list)

count_n = 1
count_m = 1
for k in range(l-1):
    if(k+1 <= len(s)):
        if k+1 == count_n*(l/n)+1:
            if(ans_str[k+1] != s[count_n]):
                ans = -1
                break
            count_n += 1
    if(k+1 <= len(t)):
        if k+1 == count_m*(l/m)+1:
            if(ans_str[k+1] != t[count_m]):
                ans = -1
                break
            count_m += 1
print("{}".format(ans))