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()
k=n*m/math.gcd(n,m)
flag=True
for i in range(math.gcd(n,m)-1):
    if s[int(k/m)*i]!=t[int(k/n)*i]:
        flag=False
        break
if flag==False:
    print(-1)
else:
    print(int(k))

Submission status: Runtime Error

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

def gcd(num1,num2):
    r=1
    while r!=0:
        r=num1%num2
        num1=num2
        num2=r
    return num1

def lcm(num1,num2):
    return num1*num2//gcd(num1,num2)

g1 = lcm(n,m)
g2 = lcm(g1//n,g1//m)

s*=g1//n
t*=g1//m

for i in range(g1//g2):
    if s[g2*i]!=t[g2*i]:
        print('-1')
        exit()
print(g1)

Submission status: Runtime Error

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

def gcd(num1,num2):
    r=1
    while r!=0:
        r=num1%num2
        num1=num2
        num2=r
    return num1

def lcm(num1,num2):
    return num1*num2//gcd(num1,num2)

g1 = lcm(n,m)
g2 = lcm(g1//n,g1//m)

s*=g1//n
t*=g1//m

for i in range(n//g2):
    if s[g2*i]!=t[g2*i]:
        print('-1')
        exit()
print(g1)

Submission status: Runtime Error

Solution code:
from math import gcd
n,m=map(int,input().split())
s=input()
t=input()
g=gcd(n,m)
ans=n*m//g
stepn=n//g
stepm=m//g
for i in range(g):
    if s[stepn*i]!=t[stepm*i]:print(-1);exit()
print(ans)

Submission status: Runtime Error

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

G = N * M // math.gcd(N, M)
slist = [i*(G//N) for i in range(N)]
mlist = [i*(G//M) for i in range(M)]
sm = set(slist) & set(mlist)
for i in sm:
    si = slist.index(i)
    mi = mlist.index(i)
    if S[si] != T[mi]:
        print(-1)
        exit()

print(G)

Submission status: Runtime Error

Solution code:
def make_divisors(n):
    divisors = set()
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.add(i)
            if i != n // i:
                divisors.add(n//i)
    return divisors

N,M = (int(x) for x in input().split())
if M > N:
    N,M = M,N
    S,T = T,S
S = list(input())
T = list(input())
dn = make_divisors(N)
dm = make_divisors(M)
dnm = dn & dm
if dnm == {1}:
    if S[0] == T[0]:
        print(N*M)
    else:
        print('-1')
else:
    gcd = max(dnm)
    n = N // gcd
    m = M // gcd
    for i in range(N//n):
        if S[n*i] != T[m*i]:
            print('-1')
            break
    else:
        print(N*M//gcd)

Submission status: Runtime Error

Solution code:
import fractions

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

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

d_N = {}

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

for m in range(M):
    d = fractions.gcd(m, M)
    k = (m // d, M // d)
    if k in d_N:
        if S[d_N[k]] != T[m]:
            print(-1)
            exit()
try:
    L = int(lcm(N, M))
except:
    print('yy')
    exit()
i = 1
while True:
    flag = True
    L_ = L * i
    a = [None] * L_
    for j in range(N):
        a[(L_ // N) * j] = S[j]
    
    for j in range(M):
        if a[(L_ // M) * j] is not None:
            if a[(L_ // M ) * j] != T[j]:
                flag = False
                break

    if flag:
        print(L_)
        exit()

    i += 1

Submission status: Runtime Error

Solution code:
import fractions

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

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

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

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

L = int(lcm(N, M))
i = 1
while True:
    flag = True
    L_ = L * i
    a = [None] * L_
    for j in range(N):
        a[(L_ // N) * j] = S[j]
    
    for j in range(M):
        if a[(L_ // M) * j] is not None:
            if a[(L_ // M )* j] != T[j]:
                flag = False
                break

    if flag:
        print(L_)
        exit()

    i += 1

Submission status: Runtime Error

Solution code:
import fractions

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

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

d_N = {}

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

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

L = int(lcm(N, M))
i = 1
while True:
    flag = True
    L_ = L * i
    a = ['0'] * L_
    for j in range(N):
        a[L_ // N * j] = S[j]
    
    for j in range(M):
        if (a[L_ // M * j] != '0') and (a[L_ // M * j] != T[j]):
            flag = False
            break

    if flag:
        print(L_)
        exit()

    i += 1

Submission status: Runtime Error

Solution code:
import fractions
from collections import defaultdict

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

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

d_N = {}

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

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

L = int(lcm(N, M))
i = 1
while True:
    flag = True
    L_ = L * i
    a = ['0'] * L_
    for j in range(N):
        a[L_ // N * j] = S[j]
    
    for j in range(M):
        if (a[L_ // M * j] != '0') and (a[L_ // M * j] != T[j]):
            flag = False
            break
        else:
            a[L_ // M * j] = T[j]

    if flag:
        print(L_)
        exit()

    i += 1

Submission status: Runtime Error

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

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import math
def lcm(x, y):
    return (x * y) // math.gcd(x, y)
def myAnswer(N:int,M:int,S:str,T:str) -> int:
   L = lcm(N,M)
   setS = [1]
   for n in range(1,N):
      setS.append(n * L//N + 1)
   setT = [1]
   for m in range(1,M):
      setT.append(m * L//M + 1)
   # print(setS,setT,L)
   for n,i in enumerate(setS):
      for m,j in enumerate(setT):
         if(i == j and S[n] != T[m]):
            # print(i,j,S[n],T[m],n,m)
            return -1
   else:
      return L

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
from fractions import gcd

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

def lcm_list(a):
    x = a[0]
    for i in range(1, len(a)):
        x = (x * a[i]) // gcd(x, a[i])
    return x

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

l = lcm(N, M)

if l==N or l==M or N[0]!=M[0]:
    print(-1)
else:
    print(l)

Submission status: Runtime Error

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

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

Submission status: Runtime Error

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

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import sys
import re
import math
import collections
import decimal
import bisect
import itertools
import fractions

import copy

# import heapq
# from collections import deque
# import decimal

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

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


# ===CODE===


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

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

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

    gcd = multiple(n, m)

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

    ans = ["@"] * (gcd + 2)
    for i, si in enumerate(s_idx):
        ans[si] = s[i]
    for i, ti in enumerate(t_idx):
        if ans[ti] != "@" and ans[ti] != t[i]:
            print(-1)
            exit(0)
    print(gcd)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import functools, fractions
 
def lcm(a, b):
	return a * b // fractions.gcd(a, b)
 
def check(L, NM):
    res = []
    for i in range(NM):
        res.append(int(i*(L/NM)+1))
    return res
 
def check2(x, L, NM):
    return int((x-1)*NM/L)
 

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


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

Submission status: Runtime Error

Solution code:
import sys
import re
import math
import collections
import decimal
import bisect
import itertools
import fractions

import copy

# import heapq
# from collections import deque
# import decimal

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

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


# ===CODE===


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

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

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



    gcd =  multiple(n, m)

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

    ans = [-1] * (gcd + 1)
    for i, si in enumerate(s_idx):
        ans[si] = s[i]
    for i, ti in enumerate(t_idx):
        if ans[ti] != -1 and ans[ti] != t[i]:
            print(-1)
            exit(0)
    print(gcd)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
import re
import math
import collections
import decimal
import bisect
import itertools
import fractions

import copy

# import heapq
# from collections import deque
# import decimal

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

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


# ===CODE===


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

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

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



    gcd =  multiple(n, m)

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

    ans = [-1] * (gcd + 1)
    for i, si in enumerate(s_idx):
        ans[si] = s[i]
    for i, ti in enumerate(t_idx):
        if ans[ti] != -1 and ans[ti] != t[i]:
            print(-1)
            exit(0)
    print(gcd)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
import re
import math
import collections
import decimal
import bisect
import itertools
import fractions

import copy

# import heapq
# from collections import deque
# import decimal

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

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


# ===CODE===


def main():
    n, m = ns()
    s = list(input())
    t = list(input())

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

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

    ans = [-1] * (gcd + 1)
    for i, si in enumerate(s_idx):
        ans[si] = s[i]
    for i, ti in enumerate(t_idx):
        if ans[ti] != -1 and ans[ti] != t[i]:
            print(-1)
            exit(0)
    print(gcd)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from fractions import gcd

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

Xlen = N * M // gcd(N, M)
X = [0] * Xlen

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

for i,t in enumerate(list(T)):
    num = i*(Xlen//M)
    if X[num] == 0 or X[num] == t:
        continue
    else:
        print(-1)
        exit()

print(Xlen)

Submission status: Runtime Error

Solution code:
from fractions import gcd

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

Xlen = N * M // gcd(N, M)
X = [0] * Xlen

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

for i,t in enumerate(list(T)):
    num = i*(Xlen//M)
    if X[num] == 0 or X[num] == t:
        continue
    else:
        print(-1)
        exit()

print(Xlen)

Submission status: Runtime Error

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

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

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

X = lcm(N,M)

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

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

Submission status: Runtime Error

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

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

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

X = lcm(N,M)

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

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

Submission status: Runtime Error

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

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

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

X = lcm(N,M)

if fractions.gcd(N,M) == 1 and S[0] == T[0]:
  print(X)
else:
  n = N // fractions.gcd(N,M)
  A = [i * n for i in range(0,N)]
  m = M // fractions.gcd(N,M)
  
  for i in range(X):
    if i // (n * m) == 0:
      if S[n] != T[m]:
        print(-1)
        break
  else:
    print(X)

Submission status: Runtime Error

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

lcm = n*m // fractions.gcd(n,m)
i = lcm
cnt = 0
while True:
    ans = [''] * i
    ai = 0
    for si in range(0,n):

        ans[ai] = s[si]
        ai += lcm//n
    ai = 0
    flg = True
    for ti in range(m):
        if ans[ai] == '' or t[ti] == ans[ai]:
            ans[ai] = t[ti]
        else:
            flg = False
            break
        ai += lcm//m
    if flg :
        print(i)
        break
    i += lcm
    cnt += 1
    if cnt == 10000:
        print(-1)
        break

Submission status: Runtime Error

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

lcm = n*m // math.gcd(n,m)
i = lcm
cnt = 0
while True:
    ans = [''] * i
    ai = 0
    for si in range(0,n):

        ans[ai] = s[si]
        ai += lcm//n
    ai = 0
    flg = True
    for ti in range(m):
        if ans[ai] == '' or t[ti] == ans[ai]:
            ans[ai] = t[ti]
        else:
            flg = False
            break
        ai += lcm//m
    if flg :
        print(i)
        break
    i += lcm
    cnt += 1
    if cnt == 10000:
        print(-1)
        break

Submission status: Runtime Error

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

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

Submission status: Runtime Error

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

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

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

s = input()
t = input()


g = gcd(m,n)

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

Submission status: Runtime Error

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

n, m = map(int, input().split())
s = input() #sys.stdin.readlineは最後が改行
t = input() #sys.stdin.readlineは最後が改行

import math

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

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


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

i = 1


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

print(L)

Submission status: Runtime Error

Solution code:
import fractions
N, M = map(int, input().split())
S = input()
T = input()
gcd = fractions.gcd(N,M)
lcm = int(N * M /gcd)
ss = int(lcm//N)
tt = int(lcm//M)

S_list = [0]*(N*M)
T_list = [0]*(N*M)
for m in range(N):
    S_list[m*ss] = S[m]
for m in range(M):
    T_list[m*tt] = T[m]
for j in range(N*M):
    if S_list[j] != 0 and T_list[j] != 0 and S_list[j] != T_list[j]:
        print(-1)
        exit()  
print(lcm)

Submission status: Runtime Error

Solution code:
import math
N, M = map(int, input().split())
S = input()
T = input()
gcd = math.gcd(N,M)
lcm = int(N * M /gcd)
ss = int(lcm//N)
tt = int(lcm//M)

S_list = [0]*(N*M)
T_list = [0]*(N*M)
for m in range(N):
    S_list[m*ss] = S[m]
for m in range(M):
    T_list[m*tt] = T[m]
for j in range(N*M):
    if S_list[j] != 0 and T_list[j] != 0 and S_list[j] != T_list[j]:
        print(-1)
        exit()  
print(lcm)

Submission status: Runtime Error

Solution code:

import math
N, M = map(int, input().split())
S = input()
T = input()
gcd = math.gcd(N,M)
lcm = int(N * M /gcd)
ss = int(lcm//N)
tt = int(lcm//M)

S_list = [0]*(N*M)
T_list = [0]*(N*M)
for m in range(N):
    S_list[m*ss] = S[m]
for m in range(M):
    T_list[m*tt] = T[m]
for j in range(N*M):
    if S_list[j] != 0 and T_list[j] != 0 and S_list[j] != T_list[j]:
        print(-1)
        exit()  
print(lcm)

Submission status: Runtime Error

Solution code:
import math
N, M = map(int, input().split())
S = input()
T = input()
lcm = int(N * M / math.gcd(N, M))
ss = int(lcm//N)
tt = int(lcm//M)
S_list = [0]*100000
T_list = [0]*100000
for m in range(N):
    S_list[m*ss] = S[m]
for m in range(M):
    T_list[m*tt] = T[m]
for j in range(100001):
    if S_list[j] != 0 and T_list[j] != 0 and S_list[j] != T_list[j]:
        print(-1)
        exit()  
print(lcm)

Submission status: Runtime Error

Solution code:
import math


N, M = map(int, input().split())
S = input()
T = input()
lcm = int(N * M / math.gcd(N, M))
ss = int(lcm//N)
tt = int(lcm//M)
S_list = [0]*1000000
T_list = [0]*1000000
for m in range(N):
    S_list[m*ss] = S[m]
for m in range(M):
    T_list[m*tt] = T[m]
for j in range(100001):
    if S_list[j] != 0 and T_list[j] != 0 and S_list[j] != T_list[j]:
        print(-1)
        exit()  
print(lcm)

Submission status: Runtime Error

Solution code:
#include<bits/stdc++.h>
using namespace std;

long long gcd(long long a,long long b){
  return b ? gcd(b,a%b) : a;
}

int main(){
  long long n,m;
  cin >> n >> m;
  string s,t;
  cin >> s;
  cin >> t;
  long long g=gcd(n,m);
  long long ans=n/g*m;
  bool ok=true;
  n=n/g;
  m=m/g;
  for(int i=0;i<g;++i){
    if(s[i*n]!=t[i*m]) ok=false;
  }

  if(ok==true){
    cout << ans << endl;
  }else{
    cout << "-1" << endl;
  }
  return 0;

}

Submission status: Runtime Error

Solution code:
import fractions

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

lcm = (n*m) // fractions.gcd(n, m)
if lcm == max(n, m):
    lcm *= 2

for i in range(1, 5):
    l = lcm * i
    x = ['-'] * l
    flg = True
    # S_check
    idx = 0
    for j in range(1, l, l//n):
        x[j-1] = s[idx]
        idx += 1
    #print(x)
    # t_check
    idx = 0
    for j in range(1, l, l//m):
        if x[j-1] == '-':
            x[j-1] = t[idx]
            idx += 1
        elif x[j-1] == t[idx]:
            idx += 1
        else:
            flg = False
            break
    #print(x)
    if flg:
        print(l)
        exit()
print(-1)

Submission status: Runtime Error

Solution code:
import fractions

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

lcm = (n*m) // fractions.gcd(n, m)
if lcm == max(n, m):
    lcm *= 2

for i in range(1, 5):
    l = lcm * i
    x = ['-'] * l
    flg = True
    # S_check
    idx = 0
    for j in range(1, 10**9, l//n):
        x[j-1] = s[idx]
        idx += 1
        if j + l//n >= l:
            break
    #print(x)
    # t_check
    idx = 0
    for j in range(1, 10**9, l//m):
        if x[j-1] == '-':
            x[j-1] = t[idx]
            idx += 1
        elif x[j-1] == t[idx]:
            idx += 1
        else:
            flg = False
            break
        if j + l//m >= l:
            break
    #print(x)
    if flg:
        print(l)
        exit()
print(-1)

Submission status: Runtime Error

Solution code:
import fractions

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

lcm = (n*m) // fractions.gcd(n, m)
if lcm == max(n, m):
    lcm *= 2

for i in range(1, 10):
    l = lcm * i
    x = ['-'] * l
    flg = True
    # S_check
    idx = 0
    for j in range(1, 10**9, l//n):
        x[j-1] = s[idx]
        idx += 1
        if j + l//n >= l:
            break
    #print(x)
    # t_check
    idx = 0
    for j in range(1, 10**9, l//m):
        if x[j-1] == '-':
            x[j-1] = t[idx]
            idx += 1
        elif x[j-1] == t[idx]:
            idx += 1
        else:
            flg = False
            break
        if j + l//m >= l:
            break
    #print(x)
    if flg:
        print(l)
        exit()
print(-1)

Submission status: Runtime Error

Solution code:
import fractions

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

lcm = (n*m) // fractions.gcd(n, m)
if lcm == max(n, m):
    lcm *= 2

for i in range(1, 100):
    l = lcm * i
    x = ['-'] * l
    flg = True
    # S_check
    idx = 0
    for j in range(1, 10**9, l//n):
        x[j-1] = s[idx]
        idx += 1
        if j + l//n >= l:
            break
    #print(x)
    # t_check
    idx = 0
    for j in range(1, 10**9, l//m):
        if x[j-1] == '-':
            x[j-1] = t[idx]
            idx += 1
        elif x[j-1] == t[idx]:
            idx += 1
        else:
            flg = False
            break
        if j + l//m >= l:
            break
    #print(x)
    if flg:
        print(l)
        exit()
print(-1)

Submission status: Runtime Error

Solution code:
import fractions

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

lcm = (n*m) // fractions.gcd(n, m)
if lcm == max(n, m):
    lcm *= 2

for i in range(1, 10**3):
    l = lcm * i
    x = ['-'] * l
    flg = True
    # S_check
    idx = 0
    for j in range(1, 10**9, l//n):
        x[j-1] = s[idx]
        idx += 1
        if j + l//n >= l:
            break
    #print(x)
    # t_check
    idx = 0
    for j in range(1, 10**9, l//m):
        if x[j-1] == '-':
            x[j-1] = t[idx]
            idx += 1
        elif x[j-1] == t[idx]:
            idx += 1
        else:
            flg = False
            break
        if j + l//m >= l:
            break
    #print(x)
    if flg:
        print(l)
        exit()
print(-1)

Submission status: Runtime Error

Solution code:
import fractions

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

lcm = (n*m) // fractions.gcd(n, m)
if lcm == max(n, m):
    lcm *= 2

for i in range(1, 10**4):
    l = lcm * i
    x = ['-'] * l
    flg = True
    # S_check
    idx = 0
    for j in range(1, 10**9, l//n):
        x[j-1] = s[idx]
        idx += 1
        if j + l//n >= l:
            break
    #print(x)
    # t_check
    idx = 0
    for j in range(1, 10**9, l//m):
        if x[j-1] == '-':
            x[j-1] = t[idx]
            idx += 1
        elif x[j-1] == t[idx]:
            idx += 1
        else:
            flg = False
            break
        if j + l//m >= l:
            break
    #print(x)
    if flg:
        print(l)
        exit()
print(-1)

Submission status: Runtime Error

Solution code:
import sys

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


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


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


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

    L = lcm(n, m)

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

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


if __name__ == '__main__':
    resolve()

Submission status: Runtime Error

Solution code:
import sys

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


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


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


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

    L = lcm(n, m)
    X = [""] * L
    for i in range(n):
        idx = i * L // n
        X[idx] = s[i]

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


if __name__ == '__main__':
    resolve()

Submission status: Runtime Error

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

from collections import gcd

def solve(N,M,S,T):
    g = gcd(N,M)
    for i in range(g):
        if S[N//g*i]!=T[M//g*i]:
            return -1
    ans = N*M//g
    return ans
print(solve(N,M,S,T))

Submission status: Runtime Error

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

from math import gcd

def solve(N,M,S,T):
    g = gcd(N,M)
    for i in range(g):
        if S[N//g*i]!=T[M//g*i]:
            return -1
    ans = N*M//g
    return ans
print(solve(N,M,S,T))

Submission status: Runtime Error

Solution code:
from fractions import gcd
n,m = map(int, input().split())
s = input()
t = input()
# Xの長さLはnとmで割り切れる
# Xの1, L/n + 1, ..., (n-1) * L/n + 1 番目の文字をつなげるとSになる
# Xの1, L/m + 1, ..., (m-1) * L/m + 1 番目の文字をつなげるとTになる

ans = [""] * (n*m//gcd(n,m))
N,M = 1,1
for i in range(len(ans)):
    if i == 0: 
        if s[i] != t[i]:
            print(-1)
            exit()
        ans[0] = s[i]
    else:
        if i % (len(ans)//n) == 0: 
            ans[i] = s[N]
            N += 1
        if i % (len(ans)//m) == 0:
            if ans[i] == "" or ans[i] == t[M]:
                ans[i] = t[M]
                M += 1
            else:
                print(-1)
                exit()
print(n*m//gcd(n,m))

Submission status: Runtime Error

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


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

s1=input()

s2=input()

len_moji = lcm(n,m)

len_s1 = []

len_s2 = []

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

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

for ix, vs1 in enumerate(len_s1):
    for jx, vs2 in enumerate(len_s2):
        if vs1 == vs2:
            if s1[ix] != s2[jx]:
                print(-1)
                exit()
print(len_moji)