Problem:


Score : 300 points

Problem Statement

You are given a string S of length N and another string T of length M.
These strings consist of lowercase English letters.

A string X is called a good string when the following conditions are all met:

Let L be the length of X. L is divisible by both N and M.

Concatenating the 1-st, (\frac{L}{N}+1)-th, (2 \times \frac{L}{N}+1)-th, ..., ((N-1)\times\frac{L}{N}+1)-th characters of X, without changing the order, results in S.

Concatenating the 1-st, (\frac{L}{M}+1)-th, (2 \times \frac{L}{M}+1)-th, ..., ((M-1)\times\frac{L}{M}+1)-th characters of X, without changing the order, results in T.

Determine if there exists a good string. If it exists, find the length of the shortest such string.

Constraints

1 \leq N,M \leq 10^5

S and T consist of lowercase English letters.

|S|=N

|T|=M

Input

Input is given from Standard Input in the following format:

N M
S
T

Output

If a good string does not exist, print -1; if it exists, print the length of the shortest such string.

Sample Input 1

3 2
acp
ae

Sample Output 1

6

For example, the string accept is a good string.
There is no good string shorter than this, so the answer is 6.

Sample Input 2

6 3
abcdef
abc

Sample Output 2

-1

Sample Input 3

15 9
dnsusrayukuaiia
dujrunuma

Sample Output 3

45



Sample input:
3 2
acp
ae


Sample output:
6

Submission status: Runtime Error

Solution code:
import itertools
import sys
import socket
from functools import lru_cache, reduce
import random
import numpy as np
import pprint

if socket.gethostname() in ['N551J', 'F551C']:
    sys.stdin = open('d1.in')


def read_int_list():
    return list(map(int, input().split()))


def read_int():
    return int(input())


def read_str_list():
    return input().split()


def read_str():
    return input()


def solve2(N, K, A, B):
    n = 2 * N
    abli = []
    for i in range(K):
        a, b = A[i], B[i]
        if a < b:
            abli.append((a, b))
        else:
            abli.append((b, a))
    flattenabli = itertools.chain.from_iterable(abli)

    cut = 10 ** 9 + 7

    unused = [1 for i in range(n + 1)]
    for a in flattenabli:
        unused[a] -= 1
    unusedacum = list(itertools.accumulate(unused))

    def modInverse(a, b, divmod=divmod):
        r0, r1, s0, s1 = a, b, 1, 0
        while r1 != 0:
            q, rtmp = divmod(r0, r1)
            stmp = s0 - q * s1
            r0, s0 = r1, s1
            r1, s1 = rtmp, stmp
        return s0 % cut

    @lru_cache(maxsize=None)
    def doubleFactorial(x):
        return reduce(lambda y, z: y * z % cut, range(x, 0, -2))

    @lru_cache(maxsize=None)
    def isSandwiched(i, j):
        return any(map(lambda k: abli[k][0] < i <= abli[k][1] <= j or i <= abli[k][0] <= j < abli[k][1], range(K)))

    nonSandwichedNums = [[] for i in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(i + 1, n + 1):
            if not isSandwiched(i, j):
                nonSandwichedNums[i].append(j)

    def numberUnderterminedBetween(i, j):
        return unusedacum[j] - unusedacum[i - 1]

    def pairCombinations(x):
        if x == 0:
            return 1
        elif x % 2 == 0:
            return doubleFactorial(x - 1)
        else:
            return 0

    def g(i, j):
        x = numberUnderterminedBetween(i, j)
        return pairCombinations(x)

    undetermined = numberUnderterminedBetween(1, n)

    ggg = [[0] * (i + 1) for i in range(n + 1)]
    for i in range(1, n + 1):
        for j in range(i + 1, n + 1):
            ggg[i].append(g(i, j))

    ans = 0
    dp = [[0] * (n + 1) for i in range(n + 1)]
    for i in range(1, n + 1):
        for j in nonSandwichedNums[i]:
            gg = ggg[i][j]
            if gg != 0:
                dp[i][j] = (ggg[i][j] - sum(
                    [dp[i][kk] * ggg[kk + 1][j] for kk in nonSandwichedNums[i] if kk < j])) % cut
            else:
                dp[i][j] = 0
            ans = (ans + dp[i][j] * pairCombinations(undetermined - numberUnderterminedBetween(i, j))) % cut

    return ans


def solve1(N, K, a, b):
    n = 2 * N
    a = [u - 1 for u in a]
    b = [u - 1 for u in b]

    M = 10 ** 9 + 7
    g = [0] * (n + 1)
    g[0] = 1
    for x in range(2, n + 1, 2):
        g[x] = (x - 1) * g[x - 2]

    # Number of paired points inside the interval [i, j]
    x = [[0] * n for i in range(n)]
    # Number of paired points strictly outside [i, j]
    y = [[0] * n for i in range(n)]
    ok = [[True] * n for i in range(n)]
    for i in range(n):
        for j in range(i + 1, n):
            for l in range(K):
                inside = (i <= a[l] <= j) + (i <= b[l] <= j)
                outside = 2 - inside
                ok[i][j] &= inside == 2 or outside == 2
                x[i][j] += inside
                y[i][j] += outside


    dp = [[0] * n for i in range(n)]
    for k in range(1, n):
        for i in range(n):
            j = i + k
            if j < n:
                if ok[i][j]:
                    rem_x = j - i + 1 - x[i][j]
                    dp[i][j] = g[rem_x] % M
                    for l in range(i + 1, j):
                        rem_z = j - l - x[l + 1][j]
                        dp[i][j] -= dp[i][l] * g[rem_z]
                        dp[i][j] %= M

    res = 0
    for i in range(n):
        for j in range(i + 1, n):
            rem_y = n - j + i - 1 - y[i][j]
            res += dp[i][j] * g[rem_y]
            res %= M

    return res


def solve():
    N, K = read_int_list()
    rows = [read_int_list() for i in range(K)]
    a = []
    b = []
    if rows:
        a, b = map(list, zip(*rows))
    return solve1(N, K, a, b)


def main():
    res = solve()
    print(res)


def check():
    Nmax = 10
    steps = 10000
    best_N = None
    best_K = None
    best_a = None
    best_b = None

    for step in range(steps):
        N = random.randint(1, Nmax)
        K = random.randint(1, N)
        l = np.random.choice(range(1, 2 * N + 1), size=2 * K, replace=False)
        l = list(map(int, l))
        a, b = l[:K], l[K:]

        output = solve1(N, K, a, b)
        expected = solve2(N, K, a, b)
        if output == expected:
            continue
        if best_N is None or (N, K, a, b) < (best_N, best_K, best_a, best_b):
            best_N, best_K, best_a, best_b = N, K, a, b

            print(N, K, a, b)
            print('output, expected:', output, ',', expected)


if __name__ == '__main__':
    random.seed(2)
    # check()
    main()

Submission status: Runtime Error

Solution code:
import math
import sys

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

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

if N==M:
    if S==T:
        print(N)
    else:
        print(-1)
else:
    B=lcm(N,M)
    for i in range(N):
        for j in range(M):
            if int(B/N*i+1)==int(B/M*j+1):
                if S[int(i)]==T[int(j)]:
                    break
                else:
                    print(-1)
                    sys.exit()

    print(B)

Submission status: Runtime Error

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

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

l = n * m // gcd(n, m)
a = l // n
b = l // m
#print(a, b)
#a(i-1) = b(j-i) -> ai = bj + (a-b)
res = False
clear_all = True
for i in range(1,n+1):
    if (a*i - (a-b)) % b != 0:
        j = a * i - (a-b)
        if not s[i-1] == t[j-1]:
            clear_all = False
if clear_all:
    res = True
if res:
    print(l)
else:
    print(-1)

Submission status: Runtime Error

Solution code:
import math
import sys

N,M=map(int,input().split())
length=N*M//math.gcd(N,M)

S=input()
T=input()

a=length//N
b=length//M
l=a*b//math.gcd(a,b)
s=l//a
t=l//b

for i in range(math.gcd(N,M)):
    if S[i*s]!=T[i*t]:
        print(-1)
        sys.exit()
print(length)

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):
  if x[i*(l//m)]!='.'and x[i*(l//m)]!=t[i]:
    print(-1)
    break
else:
  print(l)

Submission status: Runtime Error

Solution code:
from fractions import gcd
def swap(a,b):
  c=a
  a=b
  b=c
  return(a,b)
n,m=map(int,input().split())
s=input()
t=input()
o=n*m//gcd(n,m)
if m>n:
  s,t=swap(s,t)
  n,m=swap(n,m)
if not n%m:
  for i in range(m):
    if s[n//m*i]!=t[i]:
      print(-1)
      break
  else:
    print(n)
  exit()
for i in range(1,10**7):
  g=o*i
  x=['.']*g
  for j in range(n):
    x[j*(g//n)]=s[j]
  for j in range(m):
    if x[j*(g//m)]!='.'and x[j*(g//m)]!=t[j]:break
  else:
    print(len(x))
    break
else:print(-1)

Submission status: Runtime Error

Solution code:
from fraction import gcd
def swap(a,b):
  c=a
  a=b
  b=c
  return(a,b)
n,m=map(int,input().split())
s=input()
t=input()
o=n*m//gcd(n,m)
if m>n:
  s,t=swap(s,t)
  n,m=swap(n,m)
if not n%m:
  for i in range(m):
    if s[n//m*i]!=t[i]:
      print(-1)
      break
  else:
    print(n)
  exit()
for i in range(1,10**7):
  g=o*i
  x=['.']*g
  for j in range(n):
    x[j*(g//n)]=s[j]
  for j in range(m):
    if x[j*(g//m)]!='.'and x[j*(g//m)]!=t[j]:break
  else:
    print(len(x))
    break
else:print(-1)

Submission status: Runtime Error

Solution code:
#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#

"""
AGC028 B
"""

import itertools
import math

n = int(input())
ali = list(map(int, input().split()))

cut = 10**9+7


def modInverse(a, b, divmod=divmod):
    r0, r1, s0, s1 = a, b, 1, 0
    while r1 != 0:
        q, rtmp = divmod(r0, r1)
        stmp = s0-q*s1
        r0, s0 = r1, s1
        r1, s1 = rtmp, stmp
    return s0 % cut


# def factorial(n):
#     nn = 1
#     for i in range(2, n+1):
#         nn = nn*i
#     return(nn)


invlist = [modInverse(i, cut) for i in range(1, n+1)]
accuminv = list(itertools.accumulate(invlist, func=lambda x, y: x+y % cut))

ans = 0
nfact = math.factorial(n)
for i in range(n):
    sump = accuminv[i]+accuminv[n-1-i] - 1
    ans += ali[i]*sump % cut

ans = ans*nfact % cut
print(ans)

Submission status: Runtime Error

Solution code:
a,b=map(int,input().split(" "))
a1,b1=a,b
s=list(input())
t=list(input())
v=0
if a>b:
    if a%b==0:
        u=a//b
        for i in range(b):
            if s[i*u]==t[i]:
                v+=1
        if v==b:
            print(a)
        else:
            print(-1)
    else:
        while True:
            a1,b1=b1,a1%b1
            if b1==0 or b1==1:
                break
        if b1==0:
            for i in range((b//a1)-1):
                if s[(a//a1)*i]==t[(b//a1)*i]:
                    v+=1
            if v==(b//a1)-1:
                print(a*b//a1)
            else:
                print(-1)
        if b1==1:
            print(a*b)
else:
    a,b=b,a
    s,t=t,s
    a1,b1=b1,a1
    if a%b==0:
        u=a//b
        for i in range(b):
            if s[i*u]==t[i]:
                v+=1
        if v==b:
            print(a)
        else:
            print(-1)
    else:
        while True:
            a1,b1=b1,a1%b1
            if b1==0 or b1==1:
                break
        if b1==0:
            for i in range((b//a1)-1):
                if s[(a//a1)*i]==t[(b//a1)*i]:
                    v+=1
            if v==(b//a1)-1:
                print(a*b//a1)
            else:
                print(-1)
        if b1==1:
            print(a*b)

Submission status: Runtime Error

Solution code:
import fractions
n,m=map(int,input().split())
s=list(input())
t=list(input())
l=int(n*m/fractions.gcd(n,m))
x=[0]*l
for i in range(n):
    x[i*(l//n)]=s[i]
for i in range(m):
    if x[i*(l//m)]!=0 and x[i*(l//m)]!=t[i]:
        print(-1)
        break
else:
    print(l)

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
n = int(input())
wt = list(map(int, input().split()))
PN = 1
s = 0
rev = [1 / (i + 1) for i in range(n)]
for i in range(n):
    PN = (PN * (i+1)) % (10 ** 9 + 7)
    pij = 0
    pij = sum(rev[0:n-i]) + sum(rev[1:i+1])
    s += pij * wt[i]
    #print(pij)
print(round(PN*s) % (10 ** 9 + 7))

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
import math
n,m=map(int,input().split())
s=list(input())
l=n*m/math.gcd(n,m)
x=[0]*l
for i in range(n):
    x[i*(l/n)]=s[i]
for i in range(m):
    if x[i*(l/m)]!=0 and x[i*(l/m)]!=t[i]:
        print(-1)
else:
    print(l)

Submission status: Runtime Error

Solution code:
import fractions as f
g=f.gcd(list(map(int,input().split())));print(-1if input()[::n//g]!=input()[::m//g]else n*m//g)

Submission status: Runtime Error

Solution code:
import fractions as f
g=f.gcd(map(int,input().split()));print(-1if input()[::n//g]!=input()[::m//g]else n*m//g)

Submission status: Runtime Error

Solution code:
import sys
import math
N,M = [int(n) for n in input().split()]
S = str(input())
T = str(input())

def lcm(N,M):
    return(N*M/math.gcd(N,M))

if (N % M == 0 or M % N == 0):
    if S!= T:
        print(-1)
        sys.exit()
else:
    print(int(lcm(N,M)))

Submission status: Runtime Error

Solution code:
import math

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

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

if S[0] != T[0]:
    print(-1)
    #sys.exit()
lcm_NM = lcm(N, M)

tmp_L = lcm_NM

L = tmp_L
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, input().split())
S = input()
T = input()

if S[0] != T[0]:
    print(-1)
    sys.exit()
lcm_NM = lcm(N, M)

tmp_L = lcm_NM

L = tmp_L
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, input().split())
S = input()
T = input()

if S[0] != T[0]:
    print(-1)
    sys.exit()
lcm_NM = lcm(N, M)

tmp_L = lcm_NM

xn_index = [0]*(N)
xm_index = [0]*(M)  
xn_index[0] = 1
xm_index[0] = 1
for n in range(N):
    if n == 0:
        continue
    xn_index[n] = (n)*tmp_L//N+1
for m in range(1,M):
    if m == 0:
        continue
    xm_index[m] = (m)*tmp_L//M+1
n_set = set(xn_index)
m_set = set(xm_index)
matched_list = list(n_set & m_set)
if len(matched_list) == 1:
    pass
else:
    for k in matched_list:
        if (S[(k-1)*N//tmp_L]) == (T[(k-1)*M//tmp_L]):
            continue
        else:
            print(-1)
            sys.exit()
                    
L = tmp_L
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, input().split())
S = input()
T = input()

if S[0] != T[0]:
    print(-1)
    sys.exit()
lcm_NM = lcm(N, M)

tmp_L = lcm_NM

xn_index = [0]*(N)
xm_index = [0]*(M)  
xn_index[0] = 1
xm_index[0] = 1
for n in range(N):
    if n == 0:
        continue
    xn_index[n] = (n)*tmp_L//N+1
for m in range(1,M):
    if m == 0:
        continue
    xm_index[m] = (m)*tmp_L//M+1
n_set = set(xn_index)
m_set = set(xm_index)
matched_list = list(n_set & m_set)
if len(matched_list) == 0:
    pass
else:
    for k in matched_list:
        if (S[(k-1)*N//tmp_L]) == (T[(k-1)*M//tmp_L]):
            continue
        else:
            print(-1)
            sys.exit()
                    
L = tmp_L
print(L)

Submission status: Runtime Error

Solution code:
import numpy as np
N = int(input())
A = list(map(int, input().split()))
R = np.zeros(N + 1, dtype="int32")
P = np.ones(N + 1, dtype="int32")
mod = 10 ** 9 + 7

def rev(a):
    return pow(a, mod - 2, mod)
    
for n in range(N + 1):
    R[n] = (R[n - 1] + rev(n)) % mod
    if n != 0:
        P[n] = P[n - 1] * n
    
C = [(R[j] + R[N - j + 1] - 1) % mod for j in range(1, N + 1)]

print(sum([a * c for a, c in zip(C, A)]) * P[N] % mod)

Submission status: Runtime Error

Solution code:
import numpy as np
N = int(input())
A = list(map(int, input().split()))
R = np.zeros(N + 1, dtype=int)
P = np.ones(N + 1, dtype=int)
mod = 10 ** 9 + 7

def rev(a):
    return pow(a, mod - 2, mod)
    
for n in range(N + 1):
    R[n] = (R[n - 1] + rev(n)) % mod
    if n != 0:
        P[n] = P[n - 1] * n
    
C = [(R[j] + R[N - j + 1] - 1) % mod for j in range(1, N + 1)]

print(sum([a * c for a, c in zip(C, A)]) * P[N] % mod)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
#-*- coding: utf-8 -*-

from collections import defaultdict
from math import factorial as f
from fractions import gcd as g

n, m = [int (i) for i in raw_input ().split ()]
s = raw_input ()
t = raw_input ()
L = n * m / g (n, m)
l = [''] * (L + 5)
cnt = 0
ok = True
for i in range (n):
    l [i * L / n] = s [i]
for i in range (m):
    ok &= (l [i * L / m] == '' or l [i * L / m] == t [i])
    l [i * L / m] = t [i]
if not ok: L = -1
print L

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
#-*- coding: utf-8 -*-

from collections import defaultdict
from math import factorial as f
from fractions import gcd as g

n, m = [int (i) for i in raw_input ().split ()]
s = raw_input ()
t = raw_input ()
L = n * m / g (n, m)
l = [''] * (n * m + 5)
cnt = 0
ok = True
for i in range (n):
    l [i * L / n] = s [i]
for i in range (m):
    ok &= (l [i * L / m] == '' or l [i * L / m] == t [i])
    l [i * L / m] = t [i]
if not ok: L = -1
print L

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python
#-*- coding: utf-8 -*-

from collections import defaultdict
from math import factorial as f
from fractions import gcd as g

n, m = [int (i) for i in raw_input ().split ()]
s = raw_input ()
t = raw_input ()
L = n * m / g (n, m)
l = [''] * L
cnt = 0
ok = True
for i in range (n):
    l [i * L / n] = s [i]
for i in range (m):
    ok &= (l [i * L / m] == '' or l [i * L / m] == t [i])
    l [i * L / m] = t [i]
if not ok: L = -1
print L

Submission status: Runtime Error

Solution code:
import math
n,m=map(int,input().split())
s=input()
t=input()
c=0
g=math.gcd(n,m)
x=n*m//(math.gcd(n,m))
for k in range(g):
    if s[int(k*n/g)]==t[int(k*m/g)]:
        continue
    else:
        c=-1
        break
       
if c==-1:
    print(c)            
                        
else:
    print(x)

Submission status: Runtime Error

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

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

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

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

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

ans = l

e = set(a)&set(b)

for i in e:
    if c[i] == d[i]:
        1
    else:
        ans = -1
        break

if l ==n or l ==m:
    ans = -1
       
print(ans)

Submission status: Runtime Error

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

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

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

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

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

ans = l

e = set(a)&set(b)

for i in e:
    if c[i] == d[i]:
        1
    else:
        ans = -1
        break

if l ==n or l ==m:
        ans = -1
       
print(ans)

Submission status: Runtime Error

Solution code:
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a
    
N,M = map(int,Input().split())
s = input()
t = input()
g = gcd(N,M)
l = N*M//g

n = N//g
m = M//g

ans = l

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

Submission status: Runtime Error

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

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

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

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

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

ans = l

e = set(a)&set(b)

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

print(ans)

Submission status: Runtime Error

Solution code:
import math
N,M = map(int,input().split())
s = input()
t = input()
g = math.gcd(N,M)
l = N*M//g

n = N//g
m = M//g

ans = l

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

Submission status: Runtime Error

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

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

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

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

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

ans = l

e = set(a & b)

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

print(ans)

Submission status: Runtime Error

Solution code:
import math
N,M = map(int,input().split())
s = input()
t = input()
g = math.gcd(N,M)
l = N*M//g

n = N//g
m = M//g

ans = l

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

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

n = N//g
m = M//g

ans = l

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

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

n = N//g
m = M//g

ans = l

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

Submission status: Runtime Error

Solution code:
from fractions import gcd

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

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

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

print(n * m * d if f else -1)

Submission status: Runtime Error

Solution code:
from fractions import gcd

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

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

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

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

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
S = input()
T = input()
# def gcd(a, b):
#     if a < b:
#         return gcd(b, a)
#     else:
#         return a if b == 0 else gcd(b, a % b)

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


L = lcm(N, M)

r = ["*" for i in range(L)]
f = False

s_step = L // N
t_step = L // M
sL = lcm(s_step, t_step)
s = 0
t = 0

for i in range(0, L, sL):
    if i == 0:
        if S[i] == T[i]:
            continue
        else:
            f = True
            break
    else:
        s = i // s_step
        t = i // t_step
        if s > N - 1:
            break
        if t > M - 1:
            break
        if S[s] == T[t]:
            continue
        else:
            f = True
            break

if f:
    print(-1)
else:
    print(L)
N, M = map(int, input().split())
S = input()
T = input()


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


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


L = lcm(N, M)

f = False

s_step = L // N
t_step = L // M
sL = lcm(s_step, t_step)
s = 0
t = 0

for i in range(0, L, sL):
    if i == 0:
        if S[i] == T[i]:
            continue
        else:
            f = True
            break
    else:
        s = i // s_step
        t = i // t_step
        if s > N - 1:
            break
        if t > M - 1:
            break
        if S[s] == T[t]:
            continue
        else:
            f = True
            break

if f:
    print(-1)
else:
    print(L)

Submission status: Runtime Error

Solution code:
import math

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

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

d = dict()

for i in range(N):
    index = 1 + (L // N) * i
    d[index] = S[i]

for j in range(M):
    index = (1 + (L // M) * j)
    if index in d:
        if d[index] != T[j]:
            print(-1)
            exit()
print(L)

Submission status: Runtime Error

Solution code:
N, M = map(int, input().split())
S = input()
T = input()
import sys
sys.setrecursionlimit(20000)
def gcd(a, b):
    if a < b:
        return gcd(b, a)
    else:
        return a if b == 0 else gcd(b, a % b)


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


L = lcm(N, M)

r = ["*" for i in range(L)]
f = False

s_step = L // N
t_step = L // M
sL = lcm(s_step, t_step)
s = 0
t = 0

for i in range(0, L, sL):
    if i == 0:
        if S[i] == T[i]:
            continue
        else:
            f = True
            break
    else:
        s = i // s_step
        t = i // t_step
        if s > N - 1:
            break
        if t > M - 1:
            break
        if S[s] == T[t]:
            continue
        else:
            f = True
            break

if f:
    print(-1)
else:
    print(L)
N, M = map(int, input().split())
S = input()
T = input()


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


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


L = lcm(N, M)

f = False

s_step = L // N
t_step = L // M
sL = lcm(s_step, t_step)
s = 0
t = 0

for i in range(0, L, sL):
    if i == 0:
        if S[i] == T[i]:
            continue
        else:
            f = True
            break
    else:
        s = i // s_step
        t = i // t_step
        if s > N - 1:
            break
        if t > M - 1:
            break
        if S[s] == T[t]:
            continue
        else:
            f = True
            break

if f:
    print(-1)
else:
    print(L)

Submission status: Runtime Error

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


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

d = dict()

for i in range(N):
    index = 1+(L//N)*i
    d[index] = S[i]

for j in range(M):
    index = (1+(L//M)*j)
    if index in d:
        if d[index]!=T[j]:
            print(-1)
            exit()
print(L)

Submission status: Runtime Error

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


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

d = dict()

for i in range(N):
    print(1+(L//N)*i)
    index = 1+(L//N)*i
    d[index] = S[i]

for j in range(M):
    index = (1+(L//M)*j)
    if index in d:
        if d[index]!=T[j]:
            print(-1)
            exit()
print(L)

Submission status: Runtime Error

Solution code:
import math
n,m = map(int, input().split(' '))
s = input()
t = input()
g = math.gcd(n,m)
Flag = True
for i in range(n):
    if (m*i)%n == 0:
        if s[i] != t[int((i*m)/n)]:
            Flag = False
if Flag:
    print(int((n*m)/g))
else:
    print(-1)

Submission status: Runtime Error

Solution code:

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


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

ans = -1

pos_frc_N = []
for i in range(len(S)):
    pos_frc_N.append(i*(1/N))
    
pos_frc_M = []
for i in range(len(T)):
    pos_frc_M.append(i*(1/M))

overlap_N = []
overlap_M = []
for i in range(len(S)):
    if pos_frc_N[i] in pos_frc_M:
        overlap_N.append(i)
        overlap_M.append(pos_frc_M.index(pos_frc_N[i]))

tmp = 1
for i in range(len(overlap_N)):
    if  S[overlap_N[i]] != T[overlap_M[i]]:
        tmp = 0
        break

# calculate min number
    
if  tmp == 1:
    
    PF_S = factorize(N)
    PF_T = factorize(M)
    
    factor_S = []
    factor_T = []
    index_S = []
    index_T = []
    
    for i in range(len(PF_S)):
        factor_S.append(PF_S[i][0])
        index_S.append(PF_S[i][1])
    for i in PF_T:
        factor_T.append(PF_T[i][0])
        index_T.append(PF_T[i][1])
        
    overlap_factor = []
    min_index = []
    for i in range(len(factor_S)):
        if  factor_S[i] in factor_T:
            overlap_factor.append(i)
            min_index.append(min([index_S[i],index_T[i]]))
    
    ans = 1
    for i in range(len(factor_S)):
        if not factor_S[i] in overlap_factor:
            ans *= factor_S[i]*index_S[i]
        else:
            ans *= factor_S[i]*min_index[overlap_factor.index(factor_S[i])]
    for i in range(len(factor_T)):
        if not factor_T[i] in overlap_factor:
            ans *= factor_T[i]*index_T[i]
            
print(ans)

Submission status: Runtime Error

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

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

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


N =  array[0]

M =  array[1]

if N < 1:
    sys.exit()

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


if M < 1:
    sys.exit()

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

S = str(input())

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


T = str(input())

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


chars_S = list(S)

chars_T = list(T)

a = lcm(N, M)


limit = N

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

#print(limit)

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

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

    #print(b)
    #print(c)

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

print(flg)

Submission status: Runtime Error

Solution code:
import sys
import math
import time



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

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

t_start = time.time()
if S[0] != T[0]:
    print(-1)
    sys.exit()
lcm_NM = lcm(N, M)

loop_flg = True
i = 0
while loop_flg==True:
    i +=1
    tmp_L = i*lcm_NM
    
    xn_index = [0]*(N-1)
    xm_index = [0]*(M-1)  
    for n in range(N-1):
        xn_index[n] = (n+1)*tmp_L//N+1
    for m in range(M-1):
        xm_index[m] = (m+1)*tmp_L//M+1
    n_set = set(xn_index)
    m_set = set(xm_index)
    matched_list = list(n_set & m_set)
    if len(matched_list) == 0:
        break
    else:
        for k in matched_list:
            if (S[(k-1)*N//tmp_L]) == (T[(k-1)*M//tmp_L]):
                loop_flg = False
                continue
            else:
                t_elpsd = time.time() - t_start
                if t_elpsd > 1.9: 
                    print(-1)
                    sys.exit()
                else:
                    loop_flg = True
                    break
                    
L = tmp_L
print(L)

Submission status: Runtime Error

Solution code:
from fractions import gcd
import copy

alphabet = [chr(i) for i in range(97, 97 + 26)]


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


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

# Generate x canditate
x_len = lcm(n, m)
canditates_s = ["" for i in range(x_len)]
# これは参照渡しだからダメ：canditates_t = canditates_s
canditates_t = copy.copy(canditates_s) 
s_indlist = [i * int(x_len / n) for i in range(n)]
t_indlist = [i * int(x_len / m) for i in range(m)]

# Shared set
shared_set = set(s_indlist) & set(t_indlist)

# Djudge incoherence
for i in shared_set:
    if s[i] != t[i]:
        print(-1)
        exit()

# If the djudge cleared
print(x_len)