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:
from fractions import gcd
n,m=map(int,input().split())
s=input()
t=input()
p=gcd(n,m)
# ans=n*m//p
# tt=[0 for _ in range(ans)]
# for i in range(n):
# 	tt[i*(ans//n)]=ord(s[i])
# for i in range(m):
# 	if tt[i*(ans//m)]!=ord(t[i]) and tt[i*(ans//m)]!=0:
# 		print(-1)
# 		exit()
print(ans)

Submission status: Runtime Error

Solution code:
import math
n,m=map(int,input().split())
s=input()
t=input()
p=math.gcd(n,m)
ans=n*m//p
tt=[0 for _ in range(ans)]
for i in range(n):
	tt[i*(ans//n)]=s[i]
for i in range(m):
	if tt[i*(ans//m)]!=t[i] and tt[i*(ans//m)]!="":
		print(-1)
		exit()
print(ans)

Submission status: Runtime Error

Solution code:
import fractions
n,m=map(int,input().split())
s=input()
t=input()
p=fractions.gcd(n,m)
ans=n*m//p
tt=[""]*ans
for i in range(n):
	tt[i*(ans//n)]=s[i]
print(ans)

Submission status: Runtime Error

Solution code:
import fractions
n,m=map(int,input().split())
s=input()
t=input()
p=fractions.gcd(n,m)
ans=n*m//p
tt=[""]*ans
for i in range(n):
	tt[i*(ans//n)]=s[i]
for i in range(m):
	if tt[i*(ans//m)]!=t[i] and tt[i*(ans//m)]!="":
		print(-1)
		exit()
print(ans)

Submission status: Runtime Error

Solution code:
# AGC028
#from fractions import gcd
from math import gcd
def lcm(x, y):
    return (x * y) // gcd(x, y)

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

if N == 1 or M == 1:
    if N == 1:
        print(M)
    if M == 1:
        print(N)
    exit()

if N == l:
    tmp = N // M
    for i in range(tmp):
        if S[i * tmp] == T[i]:
            pass
        else:
            print(-1)
            exit()
if M == l:
    tmp = M // N
    for i in range(tmp):
        if T[i * tmp] == S[i]:
            pass
        else:
            print(-1)
            exit()

G = gcd(N, M)
if G != 1:
    for g in range(G):
        if S[g * N // G] == T[g * M // G]:
            pass
        else:
            print(-1)
            exit()
print(l)

Submission status: Runtime Error

Solution code:
import math

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

t=math.gcd(N,M)

if t==1:
  print(N*M)
elif t==min(N,M):
  print("-1")
elif:
  print(t*max(N,M))

Submission status: Runtime Error

Solution code:
import math

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

t=math.gcd(N,M)

if t==1:
  print(N*M)
elif t==min(N,M):
  print(-1)
elif:
  print(t*max(N,M))

Submission status: Runtime Error

Solution code:
import math
import bisect

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

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

NL=[0]*N
ML=[0]*M

for i in range(N):
    NL[i]=i*(A//N)


for i in range(M):
    ML[i]=i*(A//M)


ANDL = sorted(list(set(NL) & set(ML)))

for i in ANDL:
    St=bisect.bisect_left(NL,i)
    Tt=bisect.bisect_left(ML,i)
    if(S[St]!=T[Tt]):
        print("-1")
        exit()
print(A)

Submission status: Runtime Error

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

def gcd(x,y):
  if x==0:
    return y
  else:
    return gcd(y%x,x)

k=N*M//gcd(N,M)
X=[0]*k
for i,s in enumerate(S):
  X[i*k//N]=s
  
for i,t in enumerate(T):
  if X[i*k//M]==t or X[i*k//M]==0:
    pass
  else:
    print(-1)
    exit()
    
print(k)

Submission status: Runtime Error

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

def gcd(x,y):
  if x==0:
    return y
  else:
    return gcd(y%x,x)

k=N*M//gcd(N,M)
X=[0]*k
for i,s in enumerate(S):
  X[i*k//N]=s
  
for i,t in enumerate(T):
  if X[i*k//M]==t or X[i*k//M]==0:
    pass
  else:
    print(-1)
    exit()
    
print(k)

Submission status: Runtime Error

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

def gcd(x,y):
  if x==0:
    return y
  else:
    return gcd(y%x,x)

k=N*M//gcd(N,M)
X=[0]*k
for i,s in enumerate(S):
  X[i*k//N]=s
  
for i,t in enumerate(T):
  if X[i*k//M]==t or X[i*k//M]==0:
    pass
  else:
    print(-1)
    exit()
    
print(k)

Submission status: Runtime Error

Solution code:
from fractions import gcd

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

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

L = lcm(N, M)
X = [S[0]] * L
step_N = L // N
step_M = L // M

if S[0] != T[0]:
    ans = -1
elif step_N == 1 or step_M == 1:
    ans = -1
else:
    for i in range(1, N):
        X[i * step_N] = S[i]

    for i in range(1, M):
        X[i * step_M] = T[i]

    check_N = ''.join(X[::step_N])
    check_M = ''.join(X[::step_M])

    if check_N == S and check_M == T:
        ans = L
    else:
        ans = -1

print(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)
x = [""] * l

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

for i in range(0, l, l//m):
    if x[i]:
        if x[i] != t[i*m//l]:
            print(-1)
            break
    else: x[i] = t[i*m//l]
else: 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)
x = [""] * l

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

for i in range(m):
    index = i*l//m
    if x[index]:
        if x[index] != t[i]:
            print(-1)
            break
    else: x[index] = t[i]
else: print(l)

Submission status: Runtime Error

Solution code:
import fractions
N, M = map(int, input().split())
S = input()
T = input()
lcm = (N*M) // fractions.gcd(N, M)
if S[0] != T[0]:
    print(-1)
elif N == M and S != T:
    print(-1)
elif max(N, M) % min(N, M) == 0:
    if M > N:
        N, M = M, N
        S, T = T, S
    k = N // M
    for i in range(M):
        if S[i*k] != T[i]:
            print(-1)
            exit(0)
    print(lcm)
else:
    tmp = lcm // N
    tmp2 = lcm // M
    tmp_s = [""] * lcm
    for i in range(N):
        tmp_s[tmp * i] = S[i]
    for j in range(M):
        if tmp_s[tmp2 * j] != "" and tmp_s[tmp2 * j] != T[j]:
            print(-1)
            exit(0)
    print(lcm)

Submission status: Runtime Error

Solution code:
import fractions
N, M = map(int, input().split())
S = input()
T = input()
if S[0] != T[0]:
    print(-1)
elif N == M and S != T:
    print(-1)
else:
    lcm = (N*M) // fractions.gcd(N, M)
    tmp = lcm // N
    tmp2 = lcm // M
    tmp_s = [""] * lcm
    for i in range(N):
        tmp_s[tmp * i] = S[i]
    for j in range(M):
        if tmp_s[tmp2 * j] != "" and tmp_s[tmp2 * j] != T[j]:
            print(-1)
            exit(0)
    print(lcm)

Submission status: Runtime Error

Solution code:
import fractions
N, M = map(int, input().split())
S = input()
T = input()
if S[0] != T[0]:
    print(-1)
elif N == M and S != T:
    print(-1)
else:
    lcm = (N*M) // fractions.gcd(N, M)
    tmp = lcm // N
    tmp2 = lcm // M
    tmp_s = [""] * lcm
    for i in range(N):
        tmp_s[tmp * i] = S[i]
    for i in range(M):
        if tmp_s[tmp2 * i] != "" and tmp_s[tmp2 * i] != T[i]:
            print(-1)
            exit(0)
    print(lcm)

Submission status: Runtime Error

Solution code:
import fractions
N, M = map(int, input().split())
S = input()
T = input()
if S[0] != T[0]:
    print(-1)
elif N == M and S != T:
    print(-1)
else:
    lcm = N*M // fractions.gcd(N, M)
    count = 1
    tmp = lcm // N
    tmp2 = lcm // M
    flag = False

    tmp_s = [""] * (lcm)
    for i in range(N):
        tmp_s[tmp * i] = S[i]
    for i in range(M):
        if tmp_s[tmp2 * i] != "" and tmp_s[tmp2 * i] != T[i]:
            count += 1
            print(-1)
            exit(0)
    print(lcm)

Submission status: Runtime Error

Solution code:
import fractions
N, M = map(int, input().split())
S = input()
T = input()
if S[0] != T[0]:
    print(-1)
else:
    lcm = N*M // fractions.gcd(N, M)
    count = 1
    tmp = lcm // N
    tmp2 = lcm // M
    flag = False

    tmp_s = [""] * (lcm * count)
    for i in range(N):
        tmp_s[((lcm*count) // N) * i] = S[i]
    for i in range(M):
        if tmp_s[((lcm*count) // M) * i] != "" and tmp_s[((lcm*count) // M) * i] != T[i]:
            count += 1
            print(-1)
            exit(0)
    print(lcm)

Submission status: Runtime Error

Solution code:
import fractions
N, M = map(int, input().split())
S = input()
T = input()
if S[0] != T[0]:
    print(-1)
else:
    lcm = N*M // fractions.gcd(N, M)
    count = 1
    tmp = lcm // N
    tmp2 = lcm // M
    flag = False
    for _ in range(min(N, M)):
        tmp_s = [""] * (lcm * count)
        for i in range(N):
            tmp_s[((lcm*count) // N) * i] = S[i]
        for i in range(M):
            if tmp_s[((lcm*count) // M) * i] != "" and tmp_s[((lcm*count) // M) * i] != T[i]:
                count += 1
                flag = True
                break
        if flag:
            flag = False
            continue
        print(count * lcm)
        exit(0)
    print(-1)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, M: int, S: str, T: str):
    # from math import gcd
    from fractions import gcd

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

    l = lcm(N, M)

    x = [''] * l

    for i in range(N):
        x[i*(l//N)] = S[i]

    for i in range(M):
        if(x[i*(l//M)] != '' and x[i*(l//M)] != T[i]):
            print(-1)
            exit()
        else:
            x[i*(l//M)] = T[i]

    

    print(l)

    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    T = next(tokens)  # type: str
    solve(N, M, S, T)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, M: int, S: str, T: str):
    # from math import gcd
    from fractions import gcd

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

    l = lcm(N, M)

    x = [''] * l

    for i in range(N):
        x[i*(l//N)] = S[i]

    for i in range(M):
        if(x[i*(l//M)] != '' and x[i*(l//M)] != T[i]):
            print(-1)
            exit()
        else:
            x[i*(l//M)] = T[i]

    print(l)

    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    T = next(tokens)  # type: str
    solve(N, M, S, T)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, M: int, S: str, T: str):
    # from math import gcd
    from fractions import gcd

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

    l = lcm(N, M)

    x = [''] * 2*l

    for i in range(N):
        x[i*(l//N)] = S[i]

    for i in range(M):
        if(x[i*(l//M)] != '' and x[i*(l//M)] != T[i]):
            print(-1)
            exit()
        else:
            x[i*(l//M)] = T[i]

    

    print(l)

    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    T = next(tokens)  # type: str
    solve(N, M, S, T)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys


def solve(N: int, M: int, S: str, T: str):
    from math import gcd
    # from fractions import gcd

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

    l = lcm(N, M)

    x = [''] * l

    for i in range(N):
        x[i*(l//N)] = S[i]

    for i in range(M):
        if(x[i*(l//M)] != '' and x[i*(l//M)] != T[i]):
            print(-1)
            exit()
        else:
            x[i*(l//M)] = T[i]

    

    print(l)

    return


# Generated by 1.1.5 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    S = next(tokens)  # type: str
    T = next(tokens)  # type: str
    solve(N, M, S, T)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import fractions
N,M = map(int,input().split())
S = input()
T = input()
L = (N * M) // fractions.gcd(N,M)
div_N = L // N
div_M = L // M
s = [""] * L

for ss in range(N):
  if ss == 0:
    s[0] = S[0]
    if s[0] != T[0]:
      print(-1)
      exit()
  else:
    s[ss * (div_N)] = S[ss]
#print(L)
#print(s)
#print(tag)
count = 1
while div_M < L and count < M:
  if s[div_M] != "" and s[div_M] != T[count]:
      print(-1)
      exit()
  div_M += div_M
  count += 1
print(L)

Submission status: Runtime Error

Solution code:
import fractions
N,M = map(int,input().split())
S = input()
T = input()
L = (N * M) // fractions.gcd(N,M)
div_N = L // N
div_M = L // M
s = [""] * L

for ss in range(N):
  if ss == 0:
    s[0] = S[0]
    if s[0] != T[0]:
      print(-1)
      exit()
  else:
    s[ss * (div_N)] = S[ss]
#print(L)
#print(s)
#print(tag)
count = 1
while div_M < L:
  if s[div_M] != "" and s[div_M] != T[count]:
      print(-1)
      exit()
  div_M += div_M
  count += 1
print(L)

Submission status: Runtime Error

Solution code:
import fractions
N,M = map(int,input().split())
S = input()
T = input()
L = (N * M) // fractions.gcd(N,M)
div_N = L // N
div_M = L // M
tag = (div_N * div_M) // fractions.gcd(div_N,div_M)
count = tag // div_M
s = [""] * L
t = [""] * L

for ss in range(N):
  if ss == 0:
    s[0] = S[0]
    if s[0] != T[0]:
      print(-1)
      exit()
  else:
    s[ss * (div_N)] = S[ss]
#print(L)
#print(s)
#print(tag)
while tag <= L:
  if s[tag] != "" and s[tag] != T[count]:
      print(-1)
      exit()
  tag += tag
  count += count
print(L)

Submission status: Runtime Error

Solution code:
import fractions
N,M = map(int,input().split())
S = input()
T = input()
L = (N * M) // fractions.gcd(N,M)
div_N = L // N
div_M = L // M
tag = (div_N * div_M) // fractions.gcd(div_N,div_M)
count = tag // div_M
s = [""] * L
t = [""] * L

for ss in range(N):
  if ss == 0:
    s[0] = S[0]
    if s[0] != T[0]:
      print(-1)
      exit()
  else:
    s[ss * (div_N)] = S[ss]
#print(L)
#print(s)
#print(tag)
while tag < L:
  if s[tag] != "" and s[tag] != T[count]:
      print(-1)
      exit()
  tag += tag
  count += count
print(L)

Submission status: Runtime Error

Solution code:
import fractions
N,M = map(int,input().split())
S = input()
T = input()
L = (N * M) // fractions.gcd(N,M)
div_N = L // N
div_M = L // M
tag = (div_N * div_M) // fractions.gcd(div_N,div_M)
s = [""] * L
t = [""] * L

for ss in range(N):
  if ss == 0:
    s[0] = S[0]
    if s[0] != T[0]:
      print(-1)
      exit()
  else:
    s[ss * (div_N)] = S[ss]

for tt in range(M):
  if tt == 0:
    t[0] = T[0]
  else:
    t[tt * (div_M)] = T[tt]
while tag < L:
  if s[tag] != "" and s[tag] != t[tag]:
      print(-1)
      exit()
  tag += tag
print(L)

Submission status: Runtime Error

Solution code:
import fractions
import sys
sys.setrecursionlimit(100000000)
N,M = map(int,input().split())
S = input()
T = input()
X = (N * M) // fractions.gcd(N,M)

div_N = X // N
div_M = X // M  
s = [""] * X

for ss in range(N):
  if ss == 0:
    s[0] = S[0]
    if s[0] != T[0]:
      print(-1)
      exit()
  else:
    s[ss * (div_N)] = S[ss]

for tt in range(M):
  if tt == 0:
    if s[0] != T[tt]:
      print(-1)
      exit()
  else:
    pro = tt * (div_M)
    if s[pro] != "" and s[pro] != T[tt]:
      print(-1)
      exit()
print(X)

Submission status: Runtime Error

Solution code:
import fractions
N,M = map(int,input().split())
S = input()
T = input()
flag = True
X = (N * M) // fractions.gcd(N,M)

div_N = X // N
div_M = X // M  
s = [""] * X

for ss in range(N):
  if ss == 0:
    s[0] = S[0]
  else:
    s[ss * (div_N)] = S[ss]

for tt in range(M):
  if tt == 0:
    if s[0] != T[tt]:
      print(-1)
      exit()
  else:
    pro = tt * (div_M)
    if s[pro] != "" and s[pro] != T[tt]:
      print(-1)
      exit()
print(X)

Submission status: Runtime Error

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

div_N = X // N
div_M = X // M  
s = [""] * X

for ss in range(N):
  if ss == 0:
    s[0] = S[0]
    if s[0] != T[0]:
      print(-1)
      exit()
  else:
    s[ss * (div_N)] = S[ss]

for tt in range(M):
  if tt == 0:
    if s[0] != T[tt]:
      print(-1)
      exit()
  else:
    pro = tt * (div_M)
    if s[pro] != "" and s[pro] != T[tt]:
      print(-1)
      exit()
print(X)

Submission status: Runtime Error

Solution code:
import fractions
N,M = map(int,input().split())
S = input()
T = input()
flag = True
X = (N * M) // fractions.gcd(N,M)

div_N = X // N
div_M = X // M  
s = [""] * X

for ss in range(N):
  if ss == 0:
    s[0] = S[0]
  else:
    s[ss * (div_N)] = S[ss]

for tt in range(M):
  if tt == 0:
    if s[0] != T[tt]:
      print(-1)
      exit()
  else:
    pro = tt * (div_M)
    if s[pro] != "" and s[pro] != T[tt]:
      print(-1)
      exit()
print(X)

Submission status: Runtime Error

Solution code:
import sys
from collections import defaultdict
sys.setrecursionlimit(200000)
input = sys.stdin.readline

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

def gcd(x, y):
    if y > x:
        x, y = y, x
    if x % y == 0:
        return y
    return gcd(y, x % y)

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

m = [None] * l

for i in range(N):
    m[i * (l // N)] = S[i]

for i in range(M):
    index = i * (l // M)
    if m[index] == None:
        m[index] = T[i]
    elif m[index] == T[i]:
        pass
    else:
        print(-1)
        exit()

print(l)

Submission status: Runtime Error

Solution code:
from fractions import gcd
n,m=map(int,input().split())
s=input()
t=input()
g=gcd(n,m)
l=n*m//g
ans=l
L=[0]*l
p=0
for i in s:
  L[p]=i
  p+=l//n
p=0
for j in t:
  if L[p]!=0 and L[p]!=j:
    ans=-1
    break
  p+=l//m
print(ans)

Submission status: Runtime Error

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

def main():
    N, M = map(int, input().split())
    s = input().strip()
    t = input().strip()
    if M > N:
        tmp = s
        s = t
        t = tmp
        tmp = N
        N = M
        M = tmp
    # N >= Mと仮定して良い
    gcd_ = gcd(N, M)
    len_ = N * (M//gcd_)
    st = [""] * len_
    tmp = len_ // N
    for i in range(N):
        st[i*tmp] = s[i]
    ok = True
    tmp = len_ // M
    for i in range(M):
        if st[i*tmp] == "" or st[i*tmp] == t[i]:
            st[i*tmp] = t[i]
        else:
            ok = False
            break
    # print(st)
    if ok:
        print(len_)
    else:
        print(-1)

if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
import math

def main():
    N, M = map(int, input().split())
    s = input().strip()
    t = input().strip()
    if M > N:
        tmp = s
        s = t
        t = tmp
        tmp = N
        N = M
        M = tmp
    # N >= Mと仮定して良い
    gcd_ = math.gcd(N, M)
    len_ = N * (M//gcd_)
    st = [""] * len_
    tmp = len_ // N
    for i in range(N):
        st[i*tmp] = s[i]
    ok = True
    tmp = len_ // M
    for i in range(M):
        if st[i*tmp] == "" or st[i*tmp] == t[i]:
            st[i*tmp] = t[i]
        else:
            ok = False
            break
    # print(st)
    if ok:
        print(len_)
    else:
        print(-1)

if __name__ == "__main__":
    main()

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)
sl = [""] * lcm
for i in range(len(s)):
    temp = i * lcm // n
    sl[temp] = s[i]
for i in range(len(t)):
    temp = i * lcm // m
    if sl[temp] != "" and sl[temp] != t[i]:
        print(-1)
        exit()
print(lcm)

Submission status: Runtime Error

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

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

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
from fractions import gcd

def main():
    n,m = map(int,input().split())
    s = list(input())
    t = list(input())
    g = (n*m)//gcd(n,m)
    ans = [0]*(m*n)

    for i in range(n):
        ans[i*(g//n)] = s[i]

    for i in range(m):
        if ans[i*(g//m)] == 0:
            ans[i*(g//m)] = t[i]
        elif ans[i*(g//m)] == t[i]:
            pass
        else:
            print(-1)
            exit()
    print(g)
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from fractions import gcd

def main():
    n,m = map(int,input().split())
    s = list(input())
    t = list(input())
    g = (n*m)//gcd(n,m)
    ans = [0]*(s*t)

    for i in range(n):
        ans[i*(g//n)] = s[i]

    for i in range(m):
        if ans[i*(g//m)] == 0:
            ans[i*(g//m)] = t[i]
        elif ans[i*(g//m)] == t[i]:
            pass
        else:
            print(-1)
            exit()
    print(g)
if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from fractions import gcd

def main():
    n,m = map(int,input().split())
    s = list(input())
    t = list(input())
    g = (n*m)//gcd(n,m)
    ans = [0]*g

    for i in range(n):
        ans[i*(g//n)] = s[i]

    for i in range(m):

        if ans[i*(g//m)] == 0:
            ans[i*(g//m)] = t[i]
        elif ans[i*(g//m)] == t[i]:
            pass
        else:
            print(-1)
            exit()
    print(g)

if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from math import gcd
N,M=map(int,input().split())
S=input()
T=input()
s=(M//gcd(N,M))
t=(N//gcd(N,M))
SS=[i*s for i in range(N)]+["end"]
TT=[j*t for j in range(M)]+["end"]
p,q=0,0
ans=N*s
for k in range(N*s):
    if SS[p]==k:
        if TT[q]==k:
            if S[p]!=T[q]:
                ans=-1
        p+=1
    if TT[q]==k:
        q+=1
print(ans)

Submission status: Runtime Error

Solution code:
from fractions import gcd
N,M=map(int,input().split())
S=input()
T=input()
s=(M//gcd(N,M))
t=(N//gcd(N,M))
SS=[i*s for i in range(N)]
TT=[j*t for j in range(M)]
p,q=0,0
ans=N*s
for k in range(N*s):
    if k==SS[p]:
        if k==TT[q]:
            if S[p]!=T[q]:
                ans=-1
        p+=1
    if k==TT[q]:
        q+=1
print(ans)

Submission status: Runtime Error

Solution code:
from fractions import gcd
N,M=map(int,input().split())
S=input()
T=input()
s=M//gcd(N,M)
t=N//gcd(N,M)
if s==1:SS=S
else:SS=("?"*(s-1)).join(list(S))+"?"*(s-1)
if t==1:TT=T
else:TT=("?"*(t-1)).join(list(T))+"?"*(t-1)
for i in range(len(SS)):
    if SS[i]==TT[i] or SS[i]=="?" or TT[i]=="?":pass
    else:
        print(-1)
        exit()
print(len(SS))

Submission status: Runtime Error

Solution code:
from math import gcd
N,M=map(int,input().split())
S=input()
T=input()
s=M//gcd(N,M)
t=N//gcd(N,M)
if s==1:SS=S
else:SS=("?"*(s-1)).join(list(S))+"?"*(s-1)
if t==1:TT=T
else:TT=("?"*(t-1)).join(list(T))+"?"*(t-1)
for i in range(len(SS)):
    if SS[i]==TT[i] or SS[i]=="?" or TT[i]=="?":pass
    else:
        print(-1)
        exit()
print(len(SS))

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)
ans = lcm

X = [""] * (lcm+10)

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

for i in range(M):

    if X[i*lcm//M] != "":
        if X[i*lcm//M] != T[i]:
            ans = -1
            break
    
print(ans)

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)
ans = lcm

X = [""] * lcm

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

for i in range(M):

    if X[i*lcm//M] != "":
        if X[i*lcm//M] != T[i]:
            ans = -1
            break
    
print(ans)

Submission status: Runtime Error

Solution code:
def g_c_d(x, y):
    if x == 0:
        return y
    elif y == 0:
        return x
    else:
        return g_c_d(y, x % y)


def l_c_m(x, y):
    return x * y // g_c_d(x, y)


a, b = map(int, input().split())
c = input()
d = input()
f = l_c_m(a, b)
e = [""] * f
for i in range(0, f):
    if i * f // a > f - 1:
        break
    if e[i * f // a] == "":
        e[i * f // a] = c[i]
    elif e[i * f // a] != c[i]:
        print(-1)
        exit()
    if i * f // b > f - 1:
        break
    if e[i * f // b] == "":
        e[i * f // b] = d[i]
    elif e[i * f // b] != d[i]:
        print(-1)
        exit()
print(f)

Submission status: Runtime Error

Solution code:
def g_c_d(x, y):
    if x == 0:
        return y
    elif y == 0:
        return x
    else:
        return g_c_d(y, x % y)


def l_c_m(x, y):
    return x * y // g_c_d(x, y)


a, b = map(int, input().split())
c = input()
d = input()
f = l_c_m(a, b)
e = [""] * f
for i in range(0, 6):
    if i * f // a >= f - 1:
        break
    if e[i * f // a] == "":
        e[i * f // a] = c[i]
    elif e[i * f // a] != c[i]:
        print(-1)
        exit()
    if i * f // b >= f - 1:
        break
    if e[i * f // b] == "":
        e[i * f // b] = d[i]
    elif e[i * f // b] != d[i]:
        print(-1)
        exit()
print(f)

Submission status: Runtime Error

Solution code:
# AGC028
from fractions import gcd


def main():
    n, m = tuple(map(int, input().rstrip().split()))
    S, T = tuple(input().rstrip() for _ in range(2))
    l = n // gcd(n, m) * m
    x = [""] * l
    for i in range(n):  # place S in x
        j = (l // n) * i
        x[j] = S[i]

    for i in range(m):  # check T adapts to x or not
        j = (l // m) * i
        if x[j] not in ("", T[i]):
            print(-1)
            break
    else:
        print(l)


if __name__ == "__main__":
    main()

Submission status: Runtime Error

Solution code:
from sys import exit
import math
from fractions import gcd

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

N,M=map(int,input().split())
S=input()
T=input()
if S[0] != T[0]:
    print("-1")
    exit()
if N<M:
    N,M=M,N
    S,T=T,S
    

# N>M S>T
if(N%M==0):
    S2=""
    for i in range(N):
        if i%(N//M)==0 :
            S2+=S[i]
            
    if S2==T:
        print(N)
    else:
        print(-1)
    exit()

else:
    print(lcm(n,m))

Submission status: Runtime Error

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

def gcd(x, y):
    while y > 0:
        x, y = y, x%y
    return x
 
def lcm(x, y):
    return int(x/gcd(x, y)*y)

lenx = lcm(N,M)

s_list = list(S)
t_list = list(T)

baisuu_s = lenx/N
baisuu_t = lenx/M
def check():
    for i in range(0,lenx,baisuu_s):
        if i % baisuu_s==0 and i%baisuu_t == 0:
            if s_list[int(i/baisuu_s)] == t_list[int(i/baisuu_t)]:
                pass
            else:
                return False
    return True

if check():
    print(lenx)
else:
    print(-1)

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)

step1 = lcm // N
step2 = lcm // M

X = [0] * lcm

c = 0
for i in range(0, lcm, step1):
    if c >= len(S):
        break
    X[i] = S[c]
    c += 1

c = 0
for i in range(0, lcm, step2):
    if c >= len(T) or i >= len(X):
        break
    if X[i] != 0 and X[i] != T[c]:
        print(-1)
        exit()
    X[i] = T[c]
    c += 1

print(lcm)

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)

step1 = lcm // N
step2 = lcm // M

X = [0] * lcm

c = 0
for i in range(0, lcm, step1):
    X[i] = S[c]
    c += 1

c = 0
for i in range(0, lcm, step2):
    if c >= len(T) or i >= len(X):
        break
    if X[i] != 0 and X[i] != T[c]:
        print(-1)
        exit()
    X[i] = T[c]
    c += 1

print(lcm)

Submission status: Runtime Error

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

if N % M == 0 or M % N == 0:
	print(-1)
	exit()

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

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

n = l = lcm(N, M)
while True:
	rs = [0] * n

	sc, so = 0, l // N
	for s in S:
		rs[sc] = s
		sc += so

	tc, to = 0, l // M
	for t in T:
		if rs[tc] == 0:
			rs[tc] = t
		else:
			if rs[tc] != t:
				break
		tc += to
	else:
		break

	n += l

print(n)

Submission status: Runtime Error

Solution code:
import fractions
import sys
sys.setrecursionlimit(10**6)

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

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

step1 = lcm // N
step2 = lcm // M

X = [0] * lcm

c = 0
for i in range(0, lcm, step1):
    X[i] = S[c]
    c += 1

c = 0
for i in range(0, lcm, step2):
    if X[i] != 0 and X[i] != T[c]:
        print(-1)
        exit()
    X[i] = T[c]
    c += 1

print(lcm)