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: Wrong Answer

Solution code:
import fractions as math
from functools import reduce

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

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

N,M = [int(x) for x in input().split()]
S = input()
T = input()
l,s,long,short = (N,M,S,T) if N>M else (M,N,T,S)
if(S[0]!=T[0]):
    print(-1)
elif(l%s==0):
    x=l//s
    flag = True
    for i in range(x):
        if(long[i*x]!=short[i]):
            flag = False
            break
    if(flag):
        print(lcm(l,s))
    else:
        print(-1)
else:
    print(2*lcm(l,s))

Submission status: Wrong Answer

Solution code:
import fractions as math
from functools import reduce

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

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

N,M = [int(x) for x in input().split()]
S = input()
T = input()
l,s,long,short = (N,M,S,T) if N>M else (M,N,T,S)
if(S[0]!=T[0]):
    print(-1)
elif(l%s==0):
    x=l//s
    flag = True
    for i in range(x):
        if(long[i*x]!=short[i]):
            flag = False
            break
    if(flag):
        print(lcm(l,s))
    else:
        print(-1)
else:
    print(lcm(l,s))

Submission status: Wrong Answer

Solution code:
import fractions as math
from functools import reduce

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

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

N,M = [int(x) for x in input().split()]
S = input()
T = input()
if(N%M==0 or M%N==0 or S[0]!=T[0]):
    print(-1)
else:
    print(lcm(N,M))

Submission status: Wrong Answer

Solution code:
import fractions as math
from functools import reduce

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

def lcm(*numbers):
    return reduce(lcm_base, numbers, 1)

N,M = [int(x) for x in input().split()]
S = input()
T = input()
if(N%M==0 or M%N==0):
    print(-1)
else:
    print(lcm(N,M))

Submission status: Wrong Answer

Solution code:
gcd = lambda a,b: a if b==0 else gcd(b,a%b)
n,m = map(int,input().split())
s = input()
t = input()
a = m//gcd(n,m)
b = n//gcd(n,m)
if s[::a*b]==t[::a*b]:
    print(n*m//gcd(n,m))
else:
    print(-1)

Submission status: Wrong Answer

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

if s[0]!=t[0]:
	print(-1)
	exit()
	
if m==n:
	if s==t:
		print(m)
	else:
		print(-1)
	exit()
gcd=fractions.gcd(m,n)
if (gcd==m or gcd==n) and m>1 and n>1:
	shortened=""	
	if n>m:
		for i in range(m):
			shortened+=s[i*n//m]
		if shortened!=t:
			print(-1)
			exit()
	else:
		for i in range(n):
			shortened+=t[i*m//n]
		if shortened!=s:
			print(-1)
			exit()
	

print((m*n)//gcd)

Submission status: Wrong Answer

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

if s[0]!=t[0]:
	print(-1)
	exit()
gcd=fractions.gcd(m,n)
if gcd==m or gcd==n:
	shortened=""	
	if n>m:
		for i in range(m):
			shortened+=s[i*n//m]
		if shortened!=t:
			print(-1)
			exit()
	else:
		for i in range(n):
			shortened+=t[i*m//n]
		if shortened!=s:
			print(-1)
			exit()
	

print((m*n)//gcd)

Submission status: Wrong Answer

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

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


print((m*n)//gcd)

Submission status: Wrong Answer

Solution code:
from fractions import gcd

N, M = map(int, input().split())
s = input()
t = input()
g = gcd(N, M)
n, m = N//g, M//g

for i in range(g):
    if s[m*i] != t[n*i]:
        print(-1)
        exit()
print(N*M//g)

Submission status: Wrong Answer

Solution code:
from fractions import gcd

lcm = lambda x, y: x*y//gcd(x, y)

N, M = map(int, input().split())
s = input()
t = input()
l = lcm(N, M)
n, m = N//l, M//l

for i in range(l):
    if s[m*i] != t[n*i]:
        print(-1)
        exit()
print(l)

Submission status: Wrong Answer

Solution code:
from fractions import gcd

lcm = lambda x, y: x*y//gcd(x, y)

N, M = map(int, input().split())
s = input()
t = input()
l = lcm(N, M)
n, m = N//l, M//l

for i in range(l):
    if s[m*i] != t[n*i]:
        print(-1)
        exit()
print(l)

Submission status: Wrong Answer

Solution code:
from fractions import gcd

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

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

if ans == N or ans == M or gcd(N, M) == N or gcd(N, M) == M:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
from fractions import gcd

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

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

if ans == N or ans == M:
    print(-1)
else:
    print(ans)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!

import fractions
import sys

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

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

L = lcm(N, M)
'''   
dp = [-1] * (L + 10)

for i, s in enumerate(S):
    dp[i*L//N] = s

for i, t in enumerate(T):
    if dp[i*L//M] != -1:
        if dp[i*L//M] != t:
            print(-1)
            sys.exit()
print(L)
'''

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!

import fractions
import sys

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

def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
    
L = lcm(N, M)
if S[0] != T[0]:
    print(-1)
    sys.exit()
elif L == N or L == M:
    dp = [-1] * L
    for i, s in enumerate(S):
        dp[i*L//N] = s
        
    for i, t in enumerate(T):
        if dp[i*L//M] != -1 and dp[i*L//M] != t:
            print(-1)
            sys.exit()
    print(L)
else:
    print(L)

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!

import fractions
import sys

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

def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
    
L = lcm(N, M)
if S[0] != T[0]:
    print(-1)
    sys.exit()
elif L == N or L == M:
    dp = [-1] * L
    for i, s in enumerate(S):
        dp[i*L//N] = s
        
    for i, t in enumerate(T):
        if dp[i*L//M] != -1 and dp[i*L//M] != t:
            print(-1)
            sys.exit()
else:
    print(L)

Submission status: Wrong Answer

Solution code:
from itertools import accumulate
import math
from collections import deque
from collections import defaultdict
from itertools import permutations
import heapq
import bisect
from collections import Counter
from itertools import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = 10**10
from functools import reduce
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a
def lcm(a,b):
  return a*b //gcd(a,b)
n,m = map(int,input().split())
s = input()
t = input()
d = gcd(n,m)
l = lcm(n,m)
a = n//d
b = m//d
for i in range(d):
    if s[a*i]!= t[b*i]:
        print(-1)
        break
    else:
        print(l)

Submission status: Wrong Answer

Solution code:
def gcd(a, b):
    a, b = max(a, b), min(a, b)
    while (b != 0):
        a, b = b, a % b
    return a

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

Submission status: Wrong Answer

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

tmp = T
for i in range(N):
    c = ''
    if i%(L//M) == 0:
        c = T[0]
        T = T[1:]
    if i%(L//N) == 0:
        if c != '' and c != S[i]:
            print('-1')
            quit()
T = tmp
for i in range(M):
    c = ''
    if i%(L//N) == 0:
        c = S[0]
        S = S[1:]
    if i%(L//M) == 0:
        if c != '' and c != T[i]:
            print('-1')
            quit()

print(L)

Submission status: Wrong Answer

Solution code:
import fractions

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)

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

for i in range(N):
    c = ''
    if i%(L//M) == 0:
        c = T[0]
        T = T[1:]
    if i%(L//N) == 0:
        if c != '' and c != S[i]:
            print('-1')
            quit()
print(L)

Submission status: Wrong Answer

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

a = len(S)
b = len(T)



boichung = len(S)*len(T)
Sn = boichung / len(S) 
Tm = boichung / len(T)


for i in range(len(S)):
    si = i*Sn + 1
    for j in range(len(T)):
        tj = j*Tm + 1
        if ((si == tj) & (S[i] != T[j])):
            boichung = -1 
            break
print(int(boichung))

Submission status: Wrong Answer

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

a = len(S)
b = len(T)

while (a % b != 0):
	c = a % b
	a = b
	b = c
 


boichung = len(S)*len(T)/b
Sn = boichung / len(S) 
Tm = boichung / len(T)


for i in range(len(S)):
    si = i*Sn + 1
    for j in range(len(T)):
        tj = j*Tm + 1
        if ((si == tj) & (S[i] != T[j])):
            boichung = -1 
            break
print(boichung)

Submission status: Wrong Answer

Solution code:
#sys.stdin.readline()
import sys
input = sys.stdin.readline

N,M = map(int,input().split())
S = list(input())
T = list(input())
judge = 1 #1:可,0:不可

def gcd(a,b):
 while(b>0):
    a,b = b,a%b
 return a
def lcm(a,b):
 G = gcd(a,b)
 L = (a*b)//G
 return L

L = lcm(N,M)
ans = L
#metrial = [] #[Xの何番目の要素に使われるか,要素]
p,q = L//N,L//M
for i in range(L):
  if((i%p == 0)and(i%q == 0)): 
    if(S[i//p] != T[i//q]):
      ans = -1
      break
    if(i >100000):
      break
print(ans)

Submission status: Wrong Answer

Solution code:
#sys.stdin.readline()
import sys
input = sys.stdin.readline

N,M = map(int,input().split())
S = list(input())
T = list(input())
judge = 1 #1:可,0:不可

def gcd(a,b):
 while(b>0):
    a,b = b,a%b
 return a
def lcm(a,b):
 G = gcd(a,b)
 L = (a*b)//G
 return L

L = lcm(N,M)
ans = L
S_index,T_index = [],[]
#metrial = [] #[Xの何番目の要素に使われるか,要素]
p,q = L//N,L//M
for i in range(N):
  S_index.append(i*p)
for i in range(M):
  T_index.append(i*q)
material_and = list(set(S_index)&set(T_index))
for i in range(len(material_and)):
  if(S[i//p] != T[i//q]): 
    ans = -1
    break
print(ans)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
S = input()
T = input()
flag = True
def lcm(a, b): # 最小公倍数
    def gcd(a, b): # 最大公約数
        while b:
            a, b = b, a % b
        return a
    return a * b // gcd(a, b)
L = lcm(N,M)

if S[0] == T[0]:
    flag = True
else:
    flag = False
if flag:
    print(L)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
S = input()
T = input()
flag = True
def lcm(a, b): # 最小公倍数
    def gcd(a, b): # 最大公約数
        while b:
            a, b = b, a % b
        return a
    return a * b // gcd(a, b)
L = lcm(N,M)
"""
l = [-1 for i in range(L)]
for i in range(N):
    l[L//N*i] = ord(S[i])-97
for i in range(M):
    if l[L//M*i] == -1:
        l[L//M*i] = ord(T[i])-97
    elif l[L//M*i] == ord(T[i])-97:
        pass
    else:
        flag = False
"""
if S[0] == T[0] and S[N-1] == T[M-1]:
    flag = True
else:
    flag = False
if flag:
    print(L)
else:
    print(-1)

Submission status: Wrong Answer

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

g = fractions.gcd(N, M)
L = N * M // g

ss = L // M
ts = L // N
for i in range(L):
  if i % ss == 0 and i % ts == 0:
    if S[i//ss] != S[i//ts]:
      print(-1)
      sys.exit()
print(L)

Submission status: Wrong Answer

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

g = fractions.gcd(N, M)
L = N * M // g

ss = L // N
ts = L // M
for i in range(L):
  if i % ss == 0 and i % ts == 0:
    if S[i//ss] != S[i//ts]:
      print(-1)
      sys.exit()
print(L)

Submission status: Wrong Answer

Solution code:
n,m = map(int,input().split())
S = input()
T = input()

a,b = n,m
temp = 1
j = 2

while j-1 <= max(a,b):
    if a%j == 0 and b%j == 0:
        a /= j
        b /= j
        temp *= j
    elif a%j == 0:
        a /= j
        temp *=j
    elif b%j == 0:
        b /= j
        temp *=j
    else:
        j += 1

flag = True

if S == T:
    print(n)
elif n == m:
    print(-1)
elif S[0] == T[0]:
    if n%m != 0 and m%n != 0:
        print(temp)
    else:
        if n > m:
            for s,t in zip(S[::int(n/m)],T):
                if s != t:
                    print(-1)
                    flag = False
                    break
            if flag:
                print(n)
        else:
            for s,t in zip(S,T[::int(m/n)]):
                if s != t:
                    print(-1)
                    flag = False
                    break
            if flag:
                print(m)
            
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def pf(s): return print(s, flush=True)

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

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

#  N, M = 10**5, 10**5
#  S = 's'*N
#  T = 't'*M

X = lcm(N, M)
L = X
XS = ['X' for i in range(L+1)]
XT = ['X' for i in range(L+1)]

Submission status: Wrong Answer

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def pf(s): return print(s, flush=True)

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

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

#  N, M = 10**5, 10**5
#  S = 's'*N
#  T = 't'*M

X = lcm(N, M)
L = X
XS = ['X' for i in range(L+1)]
XT = ['X' for i in range(L+1)]
count = 0
LN = L/N
while True:
    XS[int(count*LN)] = S[count]
    count += 1
    if count > N-1:
        break
print(21131)

Submission status: Wrong Answer

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def pf(s): return print(s, flush=True)

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

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

#  N, M = 10**5, 10**5
#  S = 's'*N
#  T = 't'*M

X = lcm(N, M)

Submission status: Wrong Answer

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def pf(s): return print(s, flush=True)

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

N, M = LI()
S = input()
T = input()
#  N, M = 10**5, 10**5
#  S = 's'*N
print(121212)

Submission status: Wrong Answer

Solution code:
import math, string, itertools, fractions, heapq, collections, re,  array, bisect, sys, random, time, copy, functools
sys.setrecursionlimit(10**7)
inf = 10 ** 20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1, 0), (0, 1), (1, 0), (0, -1)]
ddn = [(-1, 0), (-1, 1), (0, 1), (1, 1), (1, 0), (1, -1), (0, -1), (-1, -1)]
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def pf(s): return print(s, flush=True)

def gcd(a,b):
    """Compute the greatest common divisor of a and b"""
    while b > 0:
        a, b = b, a % b
    return a
    
def lcm(a, b):
    """Compute the lowest common multiple of a and b"""
    return int(a * b / gcd(a, b))


N, M = LI()
S = input()
T = input()
#  N, M = 10**5, 10**5
#  S = 's'*N
#  T = 't'*M

X = lcm(len(S), len(T))
L = X
XS = ['X' for i in range(L+1)]
XT = ['X' for i in range(L+1)]
print(1313)

Submission status: Wrong Answer

Solution code:
from fractions import *
def lcm(x, y):
    return (x * y) // gcd(x, y)
N,M = map(int,input().split())
L = lcm(N,M)
words = [[] for i in range(L)]
S = str(input())
words[0].append(S[0])
for i in range(1,N):
    num = (L // N) * i
    words[num].append(S[i])
T = str(input())
for i in range(1,M):
    num = (L // M) * i
    if len(words[num]) == 1:
        if [T[i]] != words[num]:
            print(-1)
            exit()
    else:
        words[num].append(T[i])
print(L)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
S = input()
T = input()
def gcd(a,b):
  if a%b == 0:
    return b
  else:
    return gcd(b,a%b)
K = max(N,M)
L = min(N,M)
if gcd(K,L) == 1:
  print(K*L)
else:
  p = gcd(K,L)
  q = K*L//p
  if N == M:
    if S == T:
      print(N)
    else:
      print(-1)
  elif N > M:
    flag = True
    for j in range(p):
      cur = N*j//p
      if S[cur] != T[j*M//p]:
        flag = False
        break
    if flag:
      print(q)
    else:
      print(-1)
  else:
    flag = True
    for j in range(p):
      cur = M*j//p
      if T[cur] != S[j*N//p]:
        flag = False
        break
    if flag:
      print(q)
    else:
      print(-1)

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
S = input()
T = input()
def gcd(a,b):
  if a%b == 0:
    return b
  else:
    return gcd(b,a%b)
K = max(N,M)
L = min(N,M)
if gcd(K,L) == 1:
  print(K*L)
else:
  p = gcd(K,L)
  q = K*L//p
  if N == M:
    if S == T:
      print(N)
    else:
      print(-1)
  elif N > M:
    flag = True
    for j in range(p):
      cur = N*j//p
      if S[cur] != T[j*M//p]:
        flag = False
        break
    if flag:
      print(q)
    else:
      print(-1)
  else:
    flag = True
    for j in range(p):
      cur = M*j//p
      if S[cur] != T[j*N//p]:
        flag = False
        break
    if flag:
      print(q)
    else:
      print(-1)

Submission status: Wrong Answer

Solution code:
import fractions

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

if(len(S) < len(T)):
    tmp = S
    S = T
    T = tmp

len_S = len(S)
len_T = len(T)
ratio = len_S / len_T


assert(len_S >= len_T)


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


if(len_S % len_T):
    counter = 0

    for i in range(len_S / fractions.gcd(len_S, len_T) != 1):
        if not (S[i * len_S // (fractions.gcd(len_S, len_T))] ==
                T[i * len_T // (fractions.gcd(len_S, len_T))]):
            print(-1)
            counter += 1

            break

    if(counter == 0):
        print(lcm(len_S, len_T))

else:
    counter = 0

    for index in range(len_T):
        if not(S[int(index * ratio)] == T[int(index)]):
            print(-1)
            counter += 1

            break

    if(counter == 0):
        print(lcm(len_S, len_T))

Submission status: Wrong Answer

Solution code:
import fractions

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

if(len(S) < len(T)):
    tmp = S
    S = T
    T = tmp

len_S = len(S)
len_T = len(T)
ratio = len_S / len_T


assert(len_S >= len_T)


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


if(len_S % len_T):
    if(S[0] == T[0]):
        print(lcm(len_S, len_T))
    else:
        print(-1)

else:
    counter = 0

    for index in range(len_T):
        if not(S[int(index * ratio)] == T[int(index)]):
            print(-1)
            counter += 1

            break

    if(counter == 0):
        print(lcm(len_S, len_T))

Submission status: Wrong Answer

Solution code:
N,M = map(int,input().split())
s = input()
t = input()
def gcd(a,b):
    if b==0:
        return a
    else:
        return gcd(b,a%b)
k = gcd(max(N,M),min(N,M))
lcm = N*M // gcd(max(N,M),min(N,M))
n = N//k
m = M//k
for i in range(k-1):
    if not s[n*i]==t[m*i]:
        print(-1)
        exit()
print(lcm)

Submission status: Wrong Answer

Solution code:
from fractions import gcd
N, M = map(int, input().split())
S = input()
T = input()
gcd_ = gcd(len(S), len(T))
saisho = len(S) * len(T) // gcd_
s_ = len(S)//gcd_
t_ = len(T)//gcd_
ans = True
if gcd_ != 1:
    for i in range(gcd_):
        # print(i)
        if S[s_ * i] != T[t_ * i]:
            ans = False
            # break
if ans:
    print(saisho)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
S = input()
T = input()
 
def gcd(m, n):
    x = max(m, n)
    y = min(m, n)
    if y == 0:
        return x
    else:
        return gcd(y, x%y)
 
def lcm(m, n):
	return int(m*n/gcd(m,n))
L = lcm(N, M)

print(lcm(N, M))

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
S = input()
T = input()
 
def gcd(m, n):
    x = max(m, n)
    y = min(m, n)
    if y == 0:
        return x
    else:
        return gcd(y, x%y)
 
def lcm(m, n):
	return int(m*n/gcd(m,n))
 
print(lcm(N, M))

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

a,b  = map(int, input().split())
c = input()
d = input()
x = gcd(a, b)
x = int(a*b/x)
if(x == a or x == b):
    print(-1)
else:
    print(x)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
# GCD
def gcd(x,y):
  while y:
    x,y=y,x%y
  return x

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

a,b=map(int,input().split())
input()
input()
print(-1)

Submission status: Wrong Answer

Solution code:
# GCD
def gcd(x,y):
  while y:
    x,y=y,x%y
  return x

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

a,b=map(int,input().split())
input()
input()
if a%b==0 or b%a==0:
  print(-1)
else:
  print(int(lcm(a,b)))

Submission status: Wrong Answer

Solution code:
# GCD
def gcd(x,y):
  while y:
    x,y=y,x%y
  return x

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

a,b=map(int,input().split())
if a%b==0 or b%a==0:
  print(-1)
else:
  print(lcm(a,b))

Submission status: Wrong Answer

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

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


N_len_S, M_len_T = map(int, input().split())
S = input()
T = input()
g = gcd(N_len_S, M_len_T)
l = lcm(N_len_S, M_len_T)


ans = l
for k in range(g):
    # S[i]. T[j] : 文字列 X を構成したとき重なる文字。これらが等しければよい数字。
    i = N_len_S // l * k
    j = M_len_T // l * k
    if S[i] != T[j]:
        ans = -1
        break
print(ans)

Submission status: Wrong Answer

Solution code:
def gcd(hi, lo):
    if lo == 0:
        return hi
    return gcd(lo, hi%lo)

def lcm(hi, lo):
    return hi*lo // gcd(hi, lo)


N_len_S, M_len_T = map(int, input().split())
hi = max(N_len_S, M_len_T)
lo = min(N_len_S, M_len_T)
S = input()
T = input()

g = gcd(hi, lo)
l = lcm(hi, lo)

ans = l
for k in range(g):
    # S[i]. T[j] : 文字列 X を構成したとき重なる文字。これらが等しければよい数字。
    i = N_len_S // l * k
    j = M_len_T // l * k
    if S[i] != T[j]:
        ans = -1
        break
print(ans)

Submission status: Wrong Answer

Solution code:
def gcd(hi, lo):
    if lo == 0:
        return hi
    return gcd(lo, hi%lo)

def lcm(hi, lo):
    return hi*lo // gcd(hi, lo)


N_len_S, M_len_T = map(int, input().split())
hi = max(N_len_S, M_len_T)
lo = min(N_len_S, M_len_T)
S = input()
T = input()

mod_NM = max(N_len_S, M_len_T) % min(N_len_S, M_len_T)
if mod_NM == 0:
    # 一方が他方で割り切れる場合、良い数字が存在しない
    ans = -1
elif S[0] != T[0]:
    # 先頭の文字が異なる場合、良い数字が存在しない
    ans = -1
else:
    # 存在する場合は、長さの最小公倍数が答えと思われる
    ans = lcm(hi, lo)

print(ans)

Submission status: Wrong Answer

Solution code:
import fractions

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

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

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

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

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

print(L)

Submission status: Wrong Answer

Solution code:
import fractions


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

    if S[0] != T[0]:
        print(-1)
    else:
        print(L)


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline

a,b=map(int,input().split())
A=input().rstrip()
B=input().rstrip()

x=max(a,b)
y=min(a,b)
while x%y!=0:
    x,y=y,x%y

lcm=a*b//y
#print(lcm)

if a%b==0:
    if A==B*(a//b):
        print(a)
    else:
        print(-1)
elif b%a==0:
    if B==A*(b//a):
        print(b)
    else:
        print(-1)
else:
    if A[0]==B[0]:
        print(lcm)
    else:
        print(-1)

Submission status: Wrong Answer

Solution code:
import sys
input=sys.stdin.readline

a,b=map(int,input().split())
A=input()
B=input()

x=max(a,b)
y=min(a,b)
while x%y!=0:
    x,y=y,x%y

lcm=a*b//y
#print(lcm)

if a%b==0:
    if A==B*(a//b):
        print(a)
    else:
        print(-1)
elif b%a==0:
    if B==A*(b//a):
        print(b)
    else:
        print(-1)
else:
    if A[0]==B[0]:
        print(lcm)
    else:
        print(-1)

Submission status: Wrong Answer

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

flag = True
if m%n==0:
    for i in range(n-1):
        #print(i*m/n)
        if t[i]!=s[int(i*m/n)]:
            flag=False
            break
elif n%m ==0:
    for i in range(m-1):
        if t[i]!=s[i*n/m]:
            flag=False
            break
if flag == False:
    print(-1)
else:
    a = n+1
    a-=1
    b = m+1
    b-=1
    while n != m:
        if n>m:
            n-=m
        if n<m:
            m-=n
    print(int(a*b/m))

Submission status: Wrong Answer

Solution code:
from fractions import gcd
N,M=(int(i) for i in input().split())
S=input()
T=input()
gcd_NM=gcd(N,M)
L=(N*M//gcd_NM)
LN=[1+(L//N)*i for i in range(N)]
LM=[1+(L//M)*i for i in range(M)]
L_NM=list(set(LN)&set(LM))
A=True
print(L_NM)
for i in L_NM:
  if S[LN.index(i)]!=T[LM.index(i)]:
    A=False
    break
if A is True:
  print(L)
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
import itertools
import numpy as np
import sys
def IL(): return list(map(int,input().split()))
def SL(): return input().split()
def I(): return int(sys.stdin.readline())
def S(): return input()
def gcd(a,b):
    while b % a:
        a,b = b, a % b
    return a

N,M = IL()
s = S()
t = S()

agcd = gcd(N,M)
bgcd = N//agcd
lcm = N*M//agcd

if agcd == 1:
    print(N*M//agcd)
else:
    for i in range(agcd):
        if s[i*lcm//M] == t[i*lcm//N]:
            continue
        else:
            print(-1)
            break
    else:
        print(N*M//agcd)