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:
#!/usr/bin/env python
# -*- coding: utf-8 -*-

# AGC028：A - Two Abbreviations
import numpy as np


def main():
    n, m = [int(i) for i in raw_input().strip().split(' ')]
    s = raw_input().strip()
    t = raw_input().strip()
    l = np.lcm(n, m) # 45
    n1 = l/n # 45/15 = 3
    m1 = l/m # 45/9 = 5
    l1 = np.lcm(n1, m1) # lcm(3, 5) = 15

    # d  n  s  u  s  r  a  y  u  k  u  a  i  i  a  
    # d    u    j    r    u    n    u    m    a    
    for i in range(l/l1):
        if s[i*m1] != t[i*n1]:
            print '-1'
            return
    print str(l)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
def gcd(a, b):
    if b==0:
        return a
    else:
        return gcd(b, a%b)
N,M = map(int,input().split())
S,T = input(),input()
lcm = N*M//gcd(N,M)
s = ['*']*lcm
for i in range(N):
    n = i*(lcm//N)
    if s[n]=='*' or s[n]==S[i]:
        s[n] = S[i]
OK = True
for i in range(M):
    n = i*(lcm//M)
    if not (s[n]=='*' or s[n]==T[i]):
        OK = False
print(lcm if OK else -1)

Submission status: Runtime Error

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

N,M = map(int,input().split())
S,T = input(),input()
lcm = N*M//gcd(N,M)
s = ['*']*lcm
for i in range(N):
    n = 0 if i==0 else i*(len(s)//N)
    if s[n]=='*' or s[n]==S[i]:
        s[n] = S[i]
OK = True
for i in range(M):
    n = 0 if i==0 else i*(len(s)//M)
    if not (s[n]=='*' or s[n]==T[i]):
        OK = False
print(lcm if OK else -1)

Submission status: Runtime Error

Solution code:
import sys
import math


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


n, m = map(int, sys.stdin.readline().split())
s = sys.stdin.readline()
t = sys.stdin.readline()

l = lcm(n, m)
s_index = [((i*l//n) + 1) for i in range(n)]
t_index = [((i*l//m) + 1) for i in range(m)]
for e in s_index:
    if e in t_index:
        if s[s_index.index(e)] != t[t_index.index(e)]:
            print(-1)
            sys.exit()
print(l)

Submission status: Runtime Error

Solution code:
import sys
import math


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


n, m = map(int, sys.stdin.readline().split())
s = sys.stdin.readline()
t = sys.stdin.readline()

l = lcm(n, m)
s_index = [((i*l//n) + 1) for i in range(n)]
t_index = [((i*l//m) + 1) for i in range(m)]
for e in s_index:
    if e in t_index:
        if s[e - 1] != t[e - 1]:
            print(-1)
            sys.exit()
print(l)

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 (x * y) // gcd(x, y)

l = lcm(n, m)
memoS = [0] * (l + 1)
memoT = [0] * (l + 1)

numS = [1]
numT = [1]

for i in range(1, n):
    num = i * l // n + 1
    numS.append(num)

for i in range(1, m):
    num = i * l // m + 1
    numT.append(num)
    
dictS = {}
dictT = {}

for i in range(n):
    dictS[numS[i]] = S[i]
    memoS[numS[i]] = 3

for i in range(m):
    dictT[numT[i]] = T[i]
    memoT[numT[i]] = 1

ans = l
for i in range(l):
    if memoS[i] - memoT[i] == 2:
        if dictS[i] != dictT[i]:
            ans = -1
            break
                
print(ans)

Submission status: Runtime Error

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

# ユークリッドの互除法
def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)

length = N * M // gcd(N, M)
ans1 = ['']*length
ans2 = ['']*length

for i in range(N):
    index = i * length // N + 1
    ans1[index-1] = S[i]

for i in range(M):
    index = i * length // M + 1
    if ans1[index-1] != '' and ans1[index-1] != T[i]:
        length = -1
        break

print(length)

Submission status: Runtime Error

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

# ユークリッドの互除法
def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)

length = N * M // gcd(N, M)
ans1 = ['']*length
ans2 = ['']*length

for i in range(N):
    index = i * length // N + 1
    ans1[index-1] = S[i]

for i in range(M):
    index = i * length // M + 1
    if ans1[index-1] != '' and ans1[index-1] != T[i]:
        print(-1)
        exit()

print(length)

Submission status: Runtime Error

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

# ユークリッドの互除法
def gcd(x, y):
    if y == 0:
        return x
    else:
        return gcd(y, x % y)

length = N * M // gcd(N, M)
ans1 = ['']*length
ans2 = ['']*length

for i in range(N):
    index = i * length // N + 1
    ans1[index-1] = S[i]

for i in range(M):
    index = i * length // M + 1
    ans2[index-1] = T[i]

for s, t in zip(ans1, ans2):
    if s != '' and t != '':
        if s != t:
            print(-1)
            exit()

print(length)

Submission status: Runtime Error

Solution code:
import math

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

length = N * M // math.gcd(N, M)
ans1 = ['']*length
ans2 = ['']*length

result = ''
for i in range(N):
    index = i * length // N + 1
    ans1[index-1] = S[i]

for i in range(M):
    index = i * length // M + 1
    ans2[index-1] = T[i]

for s, t in zip(ans1, ans2):
    if s != '' and t != '':
        if s != t:
            print(-1)
            exit()

print(length)

Submission status: Runtime Error

Solution code:
from math import gcd

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

length = N * M // gcd(N, M)
ans1 = ['']*length
ans2 = ['']*length

result = ''
for i in range(N):
    index = i * length // N + 1
    ans1[index-1] = S[i]

for i in range(M):
    index = i * length // M + 1
    ans2[index-1] = T[i]

for s, t in zip(ans1, ans2):
    if s != '' and t != '':
        if s != t:
            print(-1)
            exit()

print(length)

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)
d1 = L//N
d2 = L//M
d = lcm(d1,d2)
l = list(range(L))
l = l[::d]
b = True
for i in l:
    if S[i//d1] != T[i//d2]:
        print(-1)
        sys.exit()

print(L)

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)
d1 = L//N
d2 = L//M
d = lcm(d1,d2)
l = list(range(L))
l = l[::d]
b = True
for i in l:
    if S[i//d1] != T[i//d2]:
        b = False
        break

if not b:
    L = -1
print(L)

Submission status: Runtime Error

Solution code:
import math
import pprint

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

N, M = map(int,input().split())
S = input()
T = input()
L = lcm(N,M)
d1 = L//N
d2 = L//M
d = lcm(d1,d2)
l = list(range(L))
l = l[::d]
b = True
for i in l:
    if S[i//d1] != T[i//d2]:
        b = False
        break

if not b:
    L = -1
print(L)

Submission status: Runtime Error

Solution code:
# from math import gcd
from fraction import gcd
import sys

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

d = gcd(N, M)
m = N * M // d

for i in range(d):
    if S[i * (N // d)] != T[i * (M // d)]:
        print(-1)
        sys.exit()

print(m)

Submission status: Runtime Error

Solution code:
from math import gcd
import sys

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

d = gcd(N, M)
m = N * M // d

for i in range(d):
    if S[i * (N // d)] != T[i * (M // d)]:
        print(-1)
        sys.exit()

print(m)

Submission status: Runtime Error

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

if S[0] != T[0]:ans = -1

elif N % M != 0 and M % N != 0:
    if N >= M:
        while True:
            if N * a % M == 0:
                ans = N * a
                b = int(N*a/M)
                for i in range(M):
                    if T[i] != S[b*i]:
                        ans = -1
                        break
                break
            else:
                a += 1
    elif N < M:
        while True:
            if M * a % N == 0:
                ans = M * a
                b = int(M*a/N)
                for i in range(N):
                    if S[i] != T[b*i]:
                        ans = -1
                        break
                break
            else:
                a += 1

elif N % M == 0:
    b = int(N/M)
    ans = N
    for i in range(M):
        if T[i] != S[b*i]:
            ans = -1
            break   

elif M % N == 0:
    b = int(M/N)
    ans = M
    for i in range(N):
        if S[i] != T[b*i]:
            ans = -1
            break   

print(ans)

Submission status: Runtime Error

Solution code:
import numpy as np# your code goes here
def eucrid(a, b):
	if (a > b):
		buf = a
		a = b
		b = buf
	if (b % a == 0):
		return a
	else:
		return eucrid(b%a, a)
		
def main():
	buf = input().split()
	s = input()
	t = input()
	n = len(s)
	m = len(t)
	
	big = n*m//eucrid(n, m)
	flag = big
	for i in range(big):
		if (i%(big//n) == 0 and i%(big//m) == 0):
			#print(i, n, m)
			#print((i+1)//(big//n), (i+1)//(big//m))
			if(s[(i+1)//(big//n)] != t[(i+1)//(big//m)]):
				flag = -1
				
	print(flag)
	#print(s, t, n, m)
	
	
main()

Submission status: Runtime Error

Solution code:
import numpy as np# your code goes here
def eucrid(a, b):
	if (a > b):
		buf = a
		a = b
		b = buf
	if (b % a == 0):
		return a
	else:
		return eucrid(b%a, a)
		
def main():
	buf = input().split()
	s = input()
	t = input()
	n = len(s)
	m = len(t)
	
	big = n*m//eucrid(n, m)
	flag = big
	for i in range(big):
		if (i%(big//n) == 0 and i%(big//m) == 0):
			print(i, n, m)
			print((i+1)//(big//n), (i+1)//(big//m))
			if(s[(i+1)//(big//n)] != t[(i+1)//(big//m)]):
				flag = -1
				
	print(flag)
	#print(s, t, n, m)
	
	
main()

Submission status: Runtime Error

Solution code:
from math import gcd
N, M = map(int, input().split(" "))
S = input()
T = input()
G = gcd(N, M)
L = N * M // G
for i in range(G):
  if S[i*N//G] != T[i*M//G]:
    print(-1)
    exit(0)
print(L)

Submission status: Runtime Error

Solution code:
import math
ls, lt = map(int, input().split())
s = list(input())
t = list(input())
g = math.gcd(ls,lt)
if (g == ls):
    d = lt//g
    for i in range(ls):
        if (s[i]!=t[i*d]):
            print(-1)
            exit()
elif (g == lt):
    d = ls//g
    for i in range(lt):
        if (t[i]!=s[i*d]):
            print(-1)
            exit()
print(ls*lt//g)

Submission status: Runtime Error

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

def agc(n,m,s,t):
    if s[0]!=t[0]:
        return -1
    g=fractions.gcd(n,m)
    l=n*m//g
    if s[int(l//m)]!=t[int(l//n)]:
        return -1
    return  int(l)
print(agc(n,m,s,t))

Submission status: Runtime Error

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


def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct

def agc(n,m,s,t):
    if s[0]!=t[0]:
        return -1
    g=math.gcd(n,m)
    if g==1:
        return  n*m
    l=n*m/g

    if s[int(l//m)]!=t[int(l//n)]:
        return -1
    return  int(l)
print(agc(n,m,s,t))

Submission status: Runtime Error

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

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

if N == M:
    if S == T:
        print('N')
    else:
        print(-1)
    
else:
    if S[0] == T[0]:
        lcm = a*b//(gcd(a, b))
        print(lcm)
        
        
        
        
    else:
        print(-1)

Submission status: Runtime Error

Solution code:
from math import gcd

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

nm_gcd = gcd(N, M)
n, m = M // nm_gcd, N // nm_gcd
ans = N * M // nm_gcd
for i in range(nm_gcd):
    if S[i * m] != T[i * n]:
        ans = -1
        break

print(ans)

Submission status: Runtime Error

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

x,y=map(int,input().split())
S=input()
T=input()
GCD=gcd(x,y)
LCM=(x * y) // GCD

x_new=x//GCD
y_new=y//GCD
for i in range(0,GCD-1):
  if S[(x_new)*i]==T[(y_new)*i]:
    result=LCM
  else:
    result=-1
    break
print(result)

Submission status: Runtime Error

Solution code:
import math
def removing_blocks(n, a_list):
    mod = 10 ** 9 + 7
    freq_list = [int(sum([int(math.factorial(n) / (int(abs(i - j) + 10 ** -6) + 1)) % mod for i in range(n)]) + 10 ** -6) % mod for j in range(n)]
    ret = int(sum([int((a * f) % mod) for a, f in zip(a_list, freq_list)]) % mod)
    return ret


N = int(input())
A_list = [int(a) for a in input().split()]
print(str(removing_blocks(N, A_list)))

Submission status: Runtime Error

Solution code:
def two_abbreviation(n, m, s, t):
    common = int(fractions.gcd(n, m) + 10 ** -6)
    s_common = [a for i, a in enumerate(zip(s)) if i % int(n / common + 10 ** -6) == 0]
    t_common = [a for i, a in enumerate(zip(t)) if i % int(m / common + 10 ** -6) == 0]
    if s_common == t_common:
        ret = int(n * m / common + 10 ** -6)
    else:
        ret = -1
    return ret


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

print(str(two_abbreviation(N, M, S, T)))

Submission status: Runtime Error

Solution code:
import fractions


def two_abbreviation(n, m, s, t):
    common = int(fractions.gcd(n, m) + 10 ** -6)
    s_common = [a for i, a in enumerate(zip(s)) if i % int(n / common + 10 ** -6) == 0]
    t_common = [a for i, a in enumerate(zip(t)) if i % int(m / common + 10 ** -6) == 0]
    if s_common == t_common:
        ret = int(n * m / common + 10 ** -6) 
    else:
        ret = -1
    return ret


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

print(str(two_abbreviation(N, M, S, T)))

Submission status: Runtime Error

Solution code:
import fractions


def two_abbreviation(n, m, s, t):
    common = int(fractions.gcd(n, m) + 10 ** -6)
    s_common = [a for i, a in enumerate(zip(s)) if i % int(n / common + 10 ** -6) == 0]
    t_common = [a for i, a in enumerate(zip(t)) if i % int(m / common + 10 ** -6) == 0]
    ret = int(n * m / common + 10 ** -6) if s_common == t_common else -1
    print(str(ret))


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

Submission status: Runtime Error

Solution code:
import fractions
def two_avvreviation(n, m, s, t):
    common = int(fractions.gcd(n, m) + 10 ** -6)
    s_common = [a for i, a in enumerate(zip(s)) if i % int(n / common + 10 ** -6) == 0]
    t_common = [a for i, a in enumerate(zip(t)) if i % int(m / common + 10 ** -6) == 0]
    ret = int(n * m / common + 10 ** -6) if s_common == t_common else -1
    return ret


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

print(str(two_avvreviation(N, M, S, T)))

Submission status: Runtime Error

Solution code:
import fractions
def two_avvreviation(n, m, s, t):
    common = fractions.gcd(n, m)
    s_common = [a for i, a in enumerate(zip(s)) if i % int(n / common + 10 ** -6) == 0]
    t_common = [a for i, a in enumerate(zip(t)) if i % int(m / common + 10 ** -6) == 0]
    ret = int(n * m / common + 10 ** -6) if s_common == t_common else -1
    return ret


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

print(str(two_avvreviation(N, M, S, T)))

Submission status: Runtime Error

Solution code:
import fraction
def two_avvreviation(n, m, s, t):
    common = fraction.gcd(n, m)
    s_common = [a for i, a in enumerate(zip(s)) if i % int(n / common + 10 ** -6) == 0]
    t_common = [a for i, a in enumerate(zip(t)) if i % int(m / common + 10 ** -6) == 0]
    ret = int(n * m / common + 10 ** -6) if s_common == t_common else -1
    return ret


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

print(str(two_avvreviation(N, M, S, T)))

Submission status: Runtime Error

Solution code:
import math
def two_avvreviation(n, m, s, t):
    common = math.gcd(n, m)
    s_common = [a for i, a in enumerate(zip(s)) if i % int(n / common + 10 ** -6) == 0]
    t_common = [a for i, a in enumerate(zip(t)) if i % int(m / common + 10 ** -6) == 0]
    ret = int(n * m / common + 10 ** -6) if s_common == t_common else -1
    return ret


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

print(str(two_avvreviation(N, M, S, T)))

Submission status: Runtime Error

Solution code:
def gcd(a,b): return a if b==0 else gcd(b,a%b)
def lcm(a,b): return a*b//gcd(a,b)
n,m=map(int,input().split())
s=input()
t=input()
n,m=max(n,m),min(n,m)
l=lcm(n,m)
d=[set() for i in range(l)]
f=l
for i in range(max(n,m)):
    o=i*(l//n)
    p=i*(l//m)
    if i<n: d[o].add(s[i])
    if i<m: d[p].add(t[i])
    if i<n and len(d[o])==2: f=-1
    if i<m and len(d[p])==2: f=-1
print(f)

Submission status: Runtime Error

Solution code:
def gcd(a,b): return a if b==0 else gcd(b,a%b)
def lcm(a,b): return a*b//gcd(a,b)
n,m=map(int,input().split())
s=input()
t=input()
n,m=max(n,m),min(n,m)
l=lcm(n,m)
d=[set() for i in range(l)]
f=l
for i in range(n):
    d[i*(l//n)].add(s[i])
for i in range(m):
    d[i*(l//m)].add(t[i])
for i in range(l):
    if len(d[i])==2: f=-1
print(f)

Submission status: Runtime Error

Solution code:
def gcd(a,b): return a if b==0 else gcd(b,a%b)
def lcm(a,b): return a*b//gcd(a,b)
n,m=map(int,input().split())
s=input()
t=input()
n,m=max(n,m),min(n,m)
l=lcm(n,m)
d=[set() for i in range(l)]
f=l
for i in range(n):
    d[i*n//l].add(s[i])
for i in range(m):
    d[i*m//l].add(t[i])
for i in range(l):
    if len(d[i])==2: f=-1
print(f)

Submission status: Runtime Error

Solution code:
def gcd(a,b): return a if b==0 else gcd(b,a%b)
def lcm(a,b): return a*b/gcd(a,b)
def eucl(x1,y1,x2,y2): return ((x1-x2)**2+(y1-y2)**2)**0.5
def choco(xa,ya,xb,yb,xc,yc,xd,yd): return 1 if abs((yb-ya)*(yd-yc)+(xb-xa)*(xd-xc))<1.e-10 else 0
#def pscl(num,l=[1]):
#    for i in range(num):
#        l = map(lambda x,y:x+y,[0]+l,l+[0])
#    return l

# "!/usr/bin/env pypy3
# pscl 要修正
#n=int(input())

def gcd(a,b): return a if b==0 else gcd(b,a%b)
def lcm(a,b): return a*b//gcd(a,b)
n,m=map(int,input().split())
s=input()
t=input()
n,m=max(n,m),min(n,m)
l=lcm(n,m)
d=[set() for i in range(l)]
f=l
for i in range(n):
    l[i*n].add(s[i]])
for i in range(m):
    l[i*m].add(t[i]])
for i in range(l):
    if len(l[i])==2: f=-1
print(f)

Submission status: Runtime Error

Solution code:
from fractions import gcd # python 3.4
# from math import gcd # from python 3.5 
def lcm(a,b):
    return int(a*b/gcd(a,b))

N,M = map(int, input().split())
S = input()
T = input()
L= lcm(N,M)
ans = dict()
for i in range(N):
    idx = i*(L//N)
    ans[idx] = S[i]

for j in range(M):
    idx = j*(L//M)
    if ans[idx]!="?":
        if ans[idx]==T[j]:
            continue
        else:
            print(-1)
            break
else:
    print(L)

Submission status: Runtime Error

Solution code:
from fractions import gcd # python 3.4
# from math import gcd # from python 3.5 
def lcm(a,b):
    return int(a*b/gcd(a,b))

N,M = map(int, input().split())
S = input()
T = input()
L= lcm(N,M)
ans = ["?"]*L
for i in range(N):
    idx = i*(L//N)
    ans[idx] = S[i]

for j in range(M):
    idx = j*(L//M)
    if ans[idx]!="?":
        if ans[idx]==T[j]:
            continue
        else:
            print(-1)
            break
else:
    print(L)

Submission status: Runtime Error

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


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


if N > M:
    L = N * M // gcd(N, M)
else:
    L = N * M // gcd(M, N)

p = L // N
q = L // M

U = ['a'] * L
for i in range(N):
    U[i * p] = S[i]
for i in range(M):
    U[i * q] = T[i]

if all([U[i * p] == S[i] for i in range(N)]):
    print(L)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
import sys
import fraction

N,M=map(int,input().split())
S=input()
T=input()
L=N * M // fraction.gcd(N, M)
X=["" for _ in range(L)]

if S[0] != T[0]:
    print(-1)
else:
    X[0]=S[0]
    
for i in range(1,N-1):
    x=((N-1)*L//N)+1
    if x < L:
        X[x]=S[i]
    else:
        print(-1)
        sys.exit()

for i in range(1,M-1):
    x=((M-1)*L//M)+1
    if x < L:
        if X[x] != "":
            print(-1)
            sys.exit()
    else:
        print(-1)
        sys.exit()

print(L)

Submission status: Runtime Error

Solution code:
import sys
import math

N,M=map(int,input().split())
S=input()
T=input()
L=N * M // math.gcd(N, M)
X=["" for _ in range(L)]

if S[0] != T[0]:
    print(-1)
else:
    X[0]=S[0]
    
for i in range(1,N-1):
    x=((N-1)*L//N)+1
    if x < L:
        X[x]=S[i]
    else:
        print(-1)
        sys.exit()

for i in range(1,M-1):
    x=((M-1)*L//M)+1
    if x < L:
        if X[x] != "":
            print(-1)
            sys.exit()
    else:
        print(-1)
        sys.exit()

print(L)

Submission status: Runtime Error

Solution code:
import math

N,M=map(int,input().split())
S=input()
T=input()
L=N * M // math.gcd(N, M)
X=["" for _ in range(L)]

if S[0] != T[0]:
    print(-1)
else:
    X[0]=S[0]
    
for i in range(1,N-1):
    x=((N-1)*L//N)+1
    if x < L:
        X[x]=S[i]
    else:
        print(-1)
        exit()

for i in range(1,M-1):
    x=((M-1)*L//M)+1
    if x < L:
        if X[x] != "":
            print(-1)
            exit()
    else:
        print(-1)
        exit()

print(L)

Submission status: Runtime Error

Solution code:
import math

N,M=map(int,input().split())
S=input()
T=input()
L=N * M // math.gcd(N, M)
X=["" for _ in range(L)]

if S[0] != T[0]:
    print(-1)
else:
    X[0]=S[0]
    
for i in range(1,N-1):
    x=((N-1)*L//N)+1
    if x < L:
        X[x]=S[i]
    else:
        print(-1)
        exit()

for i in range(1,M-1):
    if X[((M-1)*L//M)+1] != "":
        print(-1)
        exit()

print(L)

Submission status: Runtime Error

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


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

    g = gcd(N, M)
    for i in range(g):
        if S[i * N / g] == T[i * M / g]:
            print("-1")
            exit()
    print(N * M / g)

main()

Submission status: Runtime Error

Solution code:
n,m = map(int, input().split())
s = input()
t = input()
a1 = max(n,m)
a2 = min(n,m)
while True:
    k = a2
    a2 = a1%a2
    a1 = k
    if a2 == 0:
        b = n*m//k
        break
l = b
x = list("0"*l)
for i in range(n):
    x[i*l//n] = s[i]
for i in range(m):
    if not x[i*l//m] == "0":
        if not x[i*l//m] == t[i]:
            print("-1")
            break
else:
    print(l)

Submission status: Runtime Error

Solution code:
import fractions as frac

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

#XはL,N,Mで割り切れる
def divisionX(x):
  l = len(x)
  if( l % n == 0 & l % m == 0 ):
    return True
  
  return False

#Sになる
def link(x,d,txt):

  if(not divisionX(x)):
    return False

  l = len(x)

  ret = ''
  for i in range(0,d):
    lin = int(i * l/d + 1)
    ret += x[lin -1]

  return True if (ret == txt) else (False)

#条件

#1 最小公倍数
gcd = int( (len(s) * len(t)) / frac.gcd(len(s),len(t)) )
X = [0] * gcd

#アルファベット探索
for i in range(0,n):
  sIdx = int(i * gcd/n + 1) -1

  if( sIdx < gcd ):
    X[sIdx] = s[i]
  else:
    print('-1')
    exit()

for i in range(0,m):
  tIdx = int(i * gcd/m + 1) -1

  if( tIdx < gcd ):
    X[tIdx] = t[i]
  else:
    print('-1')
    exit()

if( link(X,n,s) & link(X,m,t) ):
  print(len(X))
else:
  print('-1')

Submission status: Runtime Error

Solution code:
import math

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

#XはL,N,Mで割り切れる
def divisionX(x):
  l = len(x)
  if( l % n == 0 & l % m == 0 ):
    return True
  
  return False

#Sになる
def link(x,d,txt):

  if(not divisionX(x)):
    return False

  l = len(x)

  ret = ''
  for i in range(0,d):
    lin = int(i * l/d + 1)
    ret += x[lin -1]

  return True if (ret == txt) else (False)

#条件

#1 最小公倍数
gcd = int( (len(s) * len(t)) / math.gcd(len(s),len(t)) )
X = [0] * gcd

#アルファベット探索
for i in range(0,n):
  sIdx = int(i * gcd/n + 1) -1

  if( sIdx < gcd ):
    X[sIdx] = s[i]
  else:
    print('-1')
    exit()

for i in range(0,m):
  tIdx = int(i * gcd/m + 1) -1

  if( tIdx < gcd ):
    X[tIdx] = t[i]
  else:
    print('-1')
    exit()

if( link(X,n,s) & link(X,m,t) ):
  print(len(X))
else:
  print('-1')

Submission status: Runtime Error

Solution code:
inp = input()
NM,S,T = [input() for i in range(inp)]


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

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

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


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

Submission status: Runtime Error

Solution code:
NM = input()
S,T = [input() for i in range(2)]


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

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

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


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

Submission status: Runtime Error

Solution code:
import math

 

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

pair = {N:S,M:T}


def lcd(n,m):
    return int(n * m / gcd(n,m))
def gcd(n,m):
    if n % m == 0:
        return m
    else:
        return gcd(m,n % m)
#    return int(m*n/math.gcd(n,m))
    
def prove(n,m):
    if gcd(n,m)==1:
        return lcd(n,m)
    global pair
    n_i = int(n/gcd(n,m))
    m_i = int(m/gcd(n,m))
    n_list = pair[n][::n_i]
    m_list = pair[m][::m_i]
#    print(c)
#    print(pair[m])
    if n_list[0:len(m_list)]==m_list:
        return lcd(n,m)
    else:
        return -1
n = max(pair.keys())
m = min(pair.keys())
if pair[N][0]!=pair[M][0]:
    print(-1)
elif N==M:
    if S==T:
        print(N)
    else
        print(-1)
else:
    print(prove(n,m))

Submission status: Runtime Error

Solution code:
import math

 

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

pair = {N:S,M:T}

def lcd(n,m):
    return int(m*n/math.gcd(n,m))
def prove(n,m):
    global pair
    mul = int(n/m)
    c = "".join([pair[n][mul*i] for i in range(len(pair[m]))])
#    print(c)
#    print(pair[m])
    if c== pair[m]:
        print (m)
    else:
        print (-1)
if max(N,M) % min(N,M) == 0:
    n = max(pair.keys())
    m = min(pair.keys())
    prove(n,m)
else:
    print(lcd(N,M))

Submission status: Runtime Error

Solution code:
import math

 

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

pair = {N:S,M:T}

def lcd(N,M):
    return int(M*N/math.gcd(N,M))
def prove(n,m):
    global pair
    mul = int(n/m)
    c = "".join([pair[n][mul*i] for i in range(len(pair[m]))])
#    print(c)
#    print(pair[m])
    if c== pair[m]:
        print (m)
    else:
        print (-1)
if max(N,M) % min(N,M) == 0:
    n = max(pair.keys())
    m = min(pair.keys())
    prove(n,m)
else:
    print(lcd(N,M))

Submission status: Runtime Error

Solution code:
import math

 

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

pair = {N:S,M:T}

def lcd(N,M):
    return int(M*N/math.gcd(N,M))
def prove(n,m):
    global pair
    mul = int(n/m)
    c = [pair[n][mul*(i-1)+1] for i in range(len(pair[m]))]
    if c== pair[m]:
        print (m)
    else:
        print (-1)
if max(N,M) % min(N,M) == 0:
    n = max(pair.keys())
    m = min(pair.keys())
    prove(n,m)
else:
    print(lcd(N,M))

Submission status: Runtime Error

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

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

lcm=int(n*m/g)

s1=int(lcm/n)
s2=int(lcm/m)

#print(s1, s2)

c=max(int(n/m), int(m/n))
f=1
for i in range(c):
    if s[s1*i] != t[s2*i]:
        f=0

if f:
    print(lcm)
else:
    print("-1")