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:
from fractions import gcd
N,M=map(int,input().split())
S=input()
T=input()

L=N*M//gcd(N,M)
#print(L)
U=["#" for _ in range(L)]
ans=L

for i in range(N):
  U[i*(L//N)]=S[i]
#print(U)

#for j in range(M):
#  if U[j*(L//M)]!="#" and U[j*(L//M)]!=T[j]:
#    ans=-1
#    break
#  else:
#    U[j*(L//M)]=T[j]

#print(U)
print(ans)

Submission status: Wrong Answer

Solution code:
import fractions
from sys import stdin

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


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


if max(n, m) % min(n, m) == 0:
    print(-1)
else:
    print(lcm(n, m))

Submission status: Wrong Answer

Solution code:
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 = list(input())
t = list(input())
g = gcd(n, m)
l = lcm(n, m)
x_s = [i for i in range(1, l, m // g)]
x_t = [i for i in range(1, l, n // g)]
j = 0
c = 1
for i in range(len(x_s)):
    if x_s[i] == x_t[j]:
        if not s[i] == t[j]:
            c = 0
    elif x_s[i] > x_t[j] and j < len(x_t):
        j += 1
print(l if c == 1 else -1)

Submission status: Wrong Answer

Solution code:
from fractions import gcd

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

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

ans = lcm

for i in range(lcm//max(N, M)):
    if S[N//lcm*i] != T[M//lcm*i]:
        ans = -1
        break
                
print(ans)

Submission status: Wrong Answer

Solution code:
from fractions import gcd

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

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

ans = lcm

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

Submission status: Wrong Answer

Solution code:
from fractions import gcd

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

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

ans = lcm

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

Submission status: Wrong Answer

Solution code:
from fractions import gcd

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

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

ans = lcm

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

Submission status: Wrong Answer

Solution code:
from fractions import gcd

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

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

ans = lcm

for i in range(lcm):
    if S[N*i//lcm] != T[M*i//lcm]:
        ans = -1
        break
                
print(ans)

Submission status: Wrong Answer

Solution code:
from fractions import gcd

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

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

ans = lcm

for i in range(lcm):
    if S[N//lcm*i] != T[M//lcm*i]:
        ans = -1
        break
                
print(ans)

Submission status: Wrong Answer

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

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()
print(-1)

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()
length = lcm(N,M)

if N<M:
    small = S
    large = T
else:
    small = T
    large = S
    
if length==len(large):
    for i in range(len(small)):
        if large[i*(len(large)//len(small))] != small[i]:
            print(-1)
            break
else:
    print(length)

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()
length = lcm(N,M)
print(length)

Submission status: Wrong Answer

Solution code:
import fractions


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

def check():
    N, M = map(int, input().split())
    S = input()
    T = input()
    length = lcm(N,M)
    print(length)

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()
length = lcm(N,M)
print(length if length!=max(N,M) else -1)

Submission status: Wrong Answer

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

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

long=lcm([n,m])

ln=int(long/n)
lm=int(long/m)

#ans=[]

ok=True

for i in range(n-1):
    if (i*ln)%lm==0:
        if s[i]!=t[(i*ln)//lm]:
            ok=False

if not ok:long=-1
print(long)

Submission status: Wrong Answer

Solution code:
import sys
N,M=map(int,input().split())
s=str(input())
t=str(input())
if N>M:
  s_=s
  s=t
  t=s_
if N==M and s==t:
  print(N)
  sys.exit()
if s in t and max(N,M)%min(N,M)==0:
  print(-1)
else:
  def gcd(a,b):
    if a==b:
      return a
    else:
      a,b=max(a,b),min(a,b)
      if a%b==0:
        return b
      else:
        return gcd(b,a%b)
  g=gcd(N,M)
  print(N*M//g)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
s=str(input())
t=str(input())
if N>M:
  s_=s
  s=t
  t=s_
if s in t and max(N,M)%min(N,M)==0:
  print(-1)
else:
  def gcd(a,b):
    if a==b:
      return a
    else:
      a,b=max(a,b),min(a,b)
      if a%b==0:
        return b
      else:
        return gcd(b,a%b)
  g=gcd(N,M)
  print(N*M//g)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
s=str(input())
t=str(input())
if N>M:
  s_=s
  s=t
  t=s_
if s in t:
  print(-1)
else:
  def gcd(a,b):
    if a==b:
      return a
    else:
      a,b=max(a,b),min(a,b)
      if a%b==0:
        return b
      else:
        return gcd(b,a%b)
  g=gcd(N,M)
  print(N*M//g)

Submission status: Wrong Answer

Solution code:
from fractions import gcd

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


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


if gcd(N, M) == 1:
    if S[0] == T[0]:
        print(lcm(N, M))
    else:
        print(-1)
else:
    L = lcm(N, M)
    for i in range(0, min(N, M), gcd(N, M) - 1):
        if S[i] == T[i]:
            continue
        else:
            print(-1)
            break
    else:
        print(L)

Submission status: Wrong Answer

Solution code:
from fractions import gcd

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


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


if gcd(N, M) == 1:
    if S[0] == T[0]:
        print(lcm(N, M))
    else:
        print(-1)
else:
    L = lcm(N, M)
    for i in range(min(N, M), gcd(N, M) - 1):
        if S[i] == T[i]:
            continue
        else:
            print(-1)
            break
    else:
        print(L)

Submission status: Wrong Answer

Solution code:
from fractions import gcd

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


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


if gcd(N, M) == 1:
    if S[0] == T[0]:
        print(lcm(N, M))
    else:
        print(-1)
else:
    L = lcm(N, M)
    for i in range(min(N, M)):
        if S[L // N * i] == T[L // M * i]:
            continue
        else:
            print(-1)
            break
    else:
        print(L)

Submission status: Wrong Answer

Solution code:
from fractions import gcd

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


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


if gcd(N, M) == 1:
    if S[0] == T[0]:
        print(lcm(N, M))
    else:
        print(-1)
else:
    L = lcm(N, M)
    for i in range(min(N, M)):
        if S[N // L * i] == T[M // L * i]:
            continue
        else:
            print(-1)
            break
    else:
        print(L)

Submission status: Wrong Answer

Solution code:
n,m = map(int, input().split())
s=str(input())
t=str(input())
def gcd(x,y):
    if x%y==0:
        return y
    else:
        return gcd(y,x%y)
g=gcd(n,m)
M=m//g
N=n//g
G=M*N//gcd(N,M)
cnt=0
i=0
if n<=m:
    while G*i<m:
        if s[i]!=t[G*i]:
            cnt+=1
            break
        i+=1
else:
    while G*i<n:
        if t[i]!=s[G*i]:
            cnt+=1
            break
        i+=1
if cnt==1:
    print(-1)
else:
    print(n*m//g)

Submission status: Wrong Answer

Solution code:
import fractions
N,M=map(int,input().split())
S=input()
T=input()
g=fractions.gcd(N,M);l=N*M//g
if(g==1):
    print(l if S[0]==T[0] else -1)
    exit()
a,b=0,0
n=N//g;m=M//g
while(a<N and b<M):
    print(a,b)
    if(S[a]!=T[b]):
        print(-1)
        exit()
    a+=n;b+=m
print(l)

Submission status: Wrong Answer

Solution code:
a,s=map(int,input().split())
sa,ss=[input() for i in range(2)]
if a<s:
    a,s=s,a
    sa,ss=ss,sa
from fractions import gcd
g=gcd(a,s)
x,y=a//g,s//g
for i in range(1,g):
    if sa[x*i]!=ss[y*i]:print(-1);break
else:print(x*s)

Submission status: Wrong Answer

Solution code:
a,s=map(int,input().split())
sa,ss=[input() for i in range(2)]
if a<s:
    a,s=s,a
    sa,ss=ss,sa
from fractions import gcd
g=gcd(a,s)
x,y=a//g,s//g
for i in range(1,s//x):
    if sa[y*i]!=ss[x*i]:print(-1);break
else:print(x*s)

Submission status: Wrong Answer

Solution code:
a,s=map(int,input().split())
b=min(a,s)
sa,ss=[input() for i in range(2)]
if ss[0]!=sa[0]:print(-1);exit()
from fractions import gcd
g=gcd(a,s)
lcm=a*s//g
step=a//g*s//g
kaburi=set()
m=0
for i in range(b):
    if ss[i]==sa[i]:
        kaburi.add(i)
        if i%step:
            continue
        m=i//step

for j in range(1,m+2):
    if {range(0,b,step*j)}-kaburi:continue
    else:print(lcm*j);exit()
print(-1)

Submission status: Wrong Answer

Solution code:
a,s=map(int,input().split())
b=min(a,s)
sa,ss=[input() for i in range(2)]
if ss[0]!=sa[0]:print(-1);exit()
from fractions import gcd
g=gcd(a,s)
lcm=a*s//g
step=a//g*s//g
kaburi=set()
m=0
for i in range(b):
    if ss[i]==sa[i]:
        kaburi.add(i)
        if i%step:
            continue
        m=i//step

for j in range(1,m+1):
    if {range(0,b,step*j)}-kaburi:continue
    else:print(lcm*j);exit()
print(-1)

Submission status: Wrong Answer

Solution code:
from fractions import gcd

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

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

L1 = [1]
L2 = [1]
for i in range(1, N):
    t = i * (L // N) + 1
    L1.append(t)

for i in range(1, M):
    t = i * (L // M) + 1
    L2.append(t)


# TMP
x = min(10**5, L)
# LS = [None] * x
# for i, li in enumerate(L1):
#     ind = li-1
#     LS[ind] = S[i]

ans = True
# for i, li in enumerate(L2):
#     ind = li-1
#     if LS[ind] is not None:
#         if LS[ind] != T[i]:
#             ans = False

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


# print(L1)
# print(L2)
# print(LS)

Submission status: Wrong Answer

Solution code:
from fractions import gcd

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

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

L1 = [1]
L2 = [1]
for i in range(1, N):
    t = i * (L // N) + 1
    L1.append(t)

for i in range(1, M):
    t = i * (L // M) + 1
    L2.append(t)


x = min(10**5, L)
LS = [None] * x
# for i, li in enumerate(L1):
#     ind = li-1
#     LS[ind] = S[i]

ans = True
# for i, li in enumerate(L2):
#     ind = li-1
#     if LS[ind] is not None:
#         if LS[ind] != T[i]:
#             ans = False

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


# print(L1)
# print(L2)
# print(LS)

Submission status: Wrong Answer

Solution code:
from fractions import gcd

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

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

L1 = [1]
L2 = [1]
for i in range(1, N):
    t = i * (L // N) + 1
    L1.append(t)

for i in range(1, M):
    t = i * (L // M) + 1
    L2.append(t)


LS = [None] * 100
# for i, li in enumerate(L1):
#     ind = li-1
#     LS[ind] = S[i]

ans = True
# for i, li in enumerate(L2):
#     ind = li-1
#     if LS[ind] is not None:
#         if LS[ind] != T[i]:
#             ans = False

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


# print(L1)
# print(L2)
# print(LS)

Submission status: Wrong Answer

Solution code:
from fractions import gcd

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

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

L1 = [1]
L2 = [1]
for i in range(1, N):
    t = i * (L // N) + 1
    L1.append(t)

for i in range(1, M):
    t = i * (L // M) + 1
    L2.append(t)


# LS = [None] * L
# for i, li in enumerate(L1):
#     ind = li-1
#     LS[ind] = S[i]

ans = True
# for i, li in enumerate(L2):
#     ind = li-1
#     if LS[ind] is not None:
#         if LS[ind] != T[i]:
#             ans = False

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


# print(L1)
# print(L2)
# print(LS)

Submission status: Wrong Answer

Solution code:
from fractions import gcd

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

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

L1 = [1]
L2 = [1]
for i in range(1, N):
    t = i * (L // N) + 1
    L1.append(t)

for i in range(1, M):
    t = i * (L // M) + 1
    L2.append(t)

## どこかにエラーがある ##########
# LS = [None] * L
# for i, li in enumerate(L1):
#     ind = li-1
#     LS[ind] = S[i]
############################

ans = True
# for i, li in enumerate(L2):
#     ind = li-1
#     if LS[ind] is not None:
#         if LS[ind] != T[i]:
#             ans = False

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


# print(L1)
# print(L2)
# print(LS)

Submission status: Wrong Answer

Solution code:
from fractions import gcd

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

L = (N * M) // gcd(N, M)
# L = 10 ** 5 + 10

L1 = [1]
L2 = [1]
for i in range(1, N):
    t = i * (L // N) + 1
    L1.append(t)

for i in range(1, M):
    t = i * (L // M) + 1
    L2.append(t)

# LS = [None] * L
# for i, li in enumerate(L1):
#     ind = li-1
#     LS[ind] = S[i]

ans = True
# for i, li in enumerate(L2):
#     ind = li-1
#     if LS[ind] is not None:
#         if LS[ind] != T[i]:
#             ans = False

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


# print(L1)
# print(L2)
# print(LS)

Submission status: Wrong Answer

Solution code:
from fractions import gcd

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

g = (N * M) // gcd(N, M)
# L = int((N * M) / gcd(N, M))
# g = gcd(N, M)
# nm = N * M
# L = nm // g
L = 10 ** 5 + 10

L1 = [1]
L2 = [1]
for i in range(1, N):
    t = i * (L // N) + 1
    L1.append(t)

for i in range(1, M):
    t = i * (L // M) + 1
    L2.append(t)

LS = [None] * L
for i, li in enumerate(L1):
    ind = li-1
    LS[ind] = S[i]

ans = True
for i, li in enumerate(L2):
    ind = li-1
    if LS[ind] is not None:
        if LS[ind] != T[i]:
            ans = False

if ans:
    print(g)
else:
    print(-1)


# print(L1)
# print(L2)
# print(LS)

Submission status: Wrong Answer

Solution code:
from fractions import gcd

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

L = (N * M) // gcd(N, M)
# L = int((N * M) / gcd(N, M))
# g = gcd(N, M)
# nm = N * M
# L = nm // g
L = 10 ** 5 + 10

L1 = [1]
L2 = [1]
for i in range(1, N):
    t = i * (L // N) + 1
    L1.append(t)

for i in range(1, M):
    t = i * (L // M) + 1
    L2.append(t)

LS = [None] * L
for i, li in enumerate(L1):
    ind = li-1
    LS[ind] = S[i]

ans = True
for i, li in enumerate(L2):
    ind = li-1
    if LS[ind] is not None:
        if LS[ind] != T[i]:
            ans = False

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


# print(L1)
# print(L2)
# print(LS)

Submission status: Wrong Answer

Solution code:
from fractions import gcd

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

# L = (N * M) // gcd(N, M)
# L = int((N * M) / gcd(N, M))
g = gcd(N, M)
nm = N * M
L = nm // g
# L = 10 ** 5 + 10

Submission status: Wrong Answer

Solution code:
from fractions import gcd

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

# L = (N * M) // gcd(N, M)
# L = int((N * M) / gcd(N, M))
g = gcd(N, M)
nm = N * M
g // nm
L = 10 ** 5 + 10

L1 = [1]
L2 = [1]
for i in range(1, N):
    t = i * (L // N) + 1
    L1.append(t)

for i in range(1, M):
    t = i * (L // M) + 1
    L2.append(t)

LS = [None] * L
for i, li in enumerate(L1):
    ind = li-1
    LS[ind] = S[i]

ans = True
for i, li in enumerate(L2):
    ind = li-1
    if LS[ind] is not None:
        if LS[ind] != T[i]:
            ans = False

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


# print(L1)
# print(L2)
# print(LS)

Submission status: Wrong Answer

Solution code:
from fractions import gcd

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

# L = (N * M) // gcd(N, M)
# L = int((N * M) / gcd(N, M))
g = gcd(N, M)
nm = N * M
L = 10 ** 5 + 10

L1 = [1]
L2 = [1]
for i in range(1, N):
    t = i * (L // N) + 1
    L1.append(t)

for i in range(1, M):
    t = i * (L // M) + 1
    L2.append(t)

LS = [None] * L
for i, li in enumerate(L1):
    ind = li-1
    LS[ind] = S[i]

ans = True
for i, li in enumerate(L2):
    ind = li-1
    if LS[ind] is not None:
        if LS[ind] != T[i]:
            ans = False

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


# print(L1)
# print(L2)
# print(LS)

Submission status: Wrong Answer

Solution code:
from fractions import gcd

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

# L = (N * M) // gcd(N, M)
# L = int((N * M) / gcd(N, M))
gcd(N, M)
L = 10 ** 5 + 10

L1 = [1]
L2 = [1]
for i in range(1, N):
    t = i * (L // N) + 1
    L1.append(t)

for i in range(1, M):
    t = i * (L // M) + 1
    L2.append(t)

LS = [None] * L
for i, li in enumerate(L1):
    ind = li-1
    LS[ind] = S[i]

ans = True
for i, li in enumerate(L2):
    ind = li-1
    if LS[ind] is not None:
        if LS[ind] != T[i]:
            ans = False

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


# print(L1)
# print(L2)
# print(LS)

Submission status: Wrong Answer

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

from fractions import gcd
# L = (N * M) // gcd(N, M)
L = 10**5+10

L1 = [1]
L2 = [1]
for i in range(1, N):
    t = i * (L // N) + 1
    L1.append(t)

for i in range(1, M):
    t = i * (L // M) + 1
    L2.append(t)

LS = [None] * L
for i, li in enumerate(L1):
    ind = li-1
    LS[ind] = S[i]

ans = True
for i, li in enumerate(L2):
    ind = li-1
    if LS[ind] is not None:
        if LS[ind] != T[i]:
            ans = False

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


# print(L1)
# print(L2)
# print(LS)

Submission status: Wrong Answer

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

# from fractions import gcd
# L = (N * M) // gcd(N, M)
L = 100

L1 = [1]
L2 = [1]
# for i in range(1, N):
#     t = i * (L // N) + 1
#     L1.append(t)

# for i in range(1, M):
#     t = i * (L // M) + 1
#     L2.append(t)

LS = [None] * L
# for i, li in enumerate(L1):
#     ind = li-1
#     LS[ind] = S[i]

ans = True
# for i, li in enumerate(L2):
#     ind = li-1
#     if LS[ind] is not None:
#         if LS[ind] != T[i]:
#             ans = False

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


# print(L1)
# print(L2)
# print(LS)

Submission status: Wrong Answer

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

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

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

if max(n,m) % min(n,m) == 0:
    print(-1)
    exit()

if s == t:
    print(n)

else:
    print(lcm(n,m))

Submission status: Wrong Answer

Solution code:
def gcd(a, b):
    if a > b:
        a, b = b, a
    while a % b != 0:
        a, b = b, a % b
    return 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)
if l == n or l == m:
    if s == t and n == m:
        print(n)
    else:
        print(-1)
else:
    print(l)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

n,m=mii()
s=ss()
t=ss()
if len(s) < len(t):
    s,t=t,s
    n,m=m,n

p=n*m//gcd(n,m)
q=gcd(n,m)
if s[0]==t[0]:
    if p!=n and p!=m:
        print(p)
    else:
        x,y=n//gcd(n,m),m//gcd(n,m)
        cnt=1
        for i in range(gcd(n,m)-1):
            if s[i*x]==t[i*y]:
                cnt+=1
        if cnt==m:
            print(n)
        else:
            print(-1)

else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

n,m=mii()
s=ss()
t=ss()
if len(s) < len(t):
    s,t=t,s
    n,m=m,n

p=n*m//gcd(n,m)
if s[0] == t[0]:
    if p!=n and p!=m:
        print(p)
    else:
        cnt=1
        for i in range(1,m):
            if s[i*p//m] == t[i]:
                cnt+=1
        if cnt==len(t):
            print(p)
        else:
            print(-1)

else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

n,m=mii()
s=ss()
t=ss()

p=n*m//gcd(n,m)
if p!=n and p!=m and (s[0] == t[0]):
    print(p)
else:
    print(-1)

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**6)
from math import floor,ceil,sqrt,factorial,log
from heapq import heappop, heappush, heappushpop
from collections import Counter,defaultdict,deque
from itertools import accumulate,permutations,combinations,product,combinations_with_replacement
from bisect import bisect_left,bisect_right
from copy import deepcopy
from operator import itemgetter
from fractions import gcd
mod = 10 ** 9 + 7
 
#整数input
def ii(): return int(sys.stdin.readline().rstrip()) #int(input())
def mii(): return map(int,sys.stdin.readline().rstrip().split())
def limii(): return list(mii()) #list(map(int,input().split()))
def lin(n:int): return [ii() for _ in range(n)]
def llint(n: int): return [limii() for _ in range(n)]
#文字列input
def ss(): return sys.stdin.readline().rstrip() #input()
def mss(): return sys.stdin.readline().rstrip().split()
def limss(): return list(mss()) #list(input().split())
def lst(n:int): return [ss() for _ in range(n)]
def llstr(n: int): return [limss() for _ in range(n)]

#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？
#本当に貪欲法か？ DP法では？？

n,m=mii()
s=ss()
t=ss()

p=n*m//gcd(n,m)
if p!=n and p!=m:
    print(p)
else:
    print(-1)

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)
for i in range(min(n, m)):
    if i % n == 0 and i % m == 0:
        if s[i // n] != t[i // m]:
            print(-1)
            break
    if i + 1 == l: print(l)

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)
for i in range(l):
    if i % n == 0 and i % m == 0:
        if s[i // n] != t[i // n]:
            print(-1)
            break
    if i + 1 == l: print(l)

Submission status: Wrong Answer

Solution code:
def main():
    N, M = (int(i) for i in input().split())
    S = input()
    T = input()

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

    def lcm(x, y):
        return x*y//gcd(x, y)
    L = lcm(N, M)
    if L == N or L == M:
        print(-1)
    else:
        print(L)


if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

#a,bの最大公約数
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

#a,bの最小公倍数
def lcm(a, b):
    return a * b // gcd (a, b)

l = lcm(n, m)
step = max(l//n, l//m)

for i in range(1, l, step):
    if i % (l//n) == 0 and i % (l//m) == 0:
        if s[i * n // l] != t[i * m // l]:
            print(-1)
            exit()
            # sys.exit(0)

print(l)

Submission status: Wrong Answer

Solution code:
from sys import stdin
import fractions

#最小公倍数
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)

n,m = [int(x) for x in stdin.readline().rstrip().split()]
s = stdin.readline().rstrip()
t = stdin.readline().rstrip()
koubai = lcm(n,m)

n_k = koubai//n
m_k = koubai//m

print(koubai)

Submission status: Wrong Answer

Solution code:
from fractions import gcd
n,m = map(int,input().split())
s = input()
t = input()
x = gcd(n,m)
if s[::n//x]==t[::m//x]:
  print(x)
else:
  print(-1)

Submission status: Wrong Answer

Solution code:
from fractions import gcd
n, m = map(int, input().split())
s = input()
t = input()
g = gcd(n, m)
sg, tg = n//g, m//g
for i in range(g-1):
  if s[sg*i] != t[tg*i]:
    print(-1)
    break
else:
  print(sg*m)

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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

Submission status: Wrong Answer

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