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

Solution (Python):
def Euclidean(a, b):
    if a<b:
        a, b = b, a
    while True:
        m = a%b
        if m==0 or b==1:
            return b
        a = b
        b = m

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

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

gcm = Euclidean(N, M)
gcd = int(N*M/gcm)


if N<M:
    N, M = M, N
    S, T = T, S



a = int(gcd/M)
b = int(gcd/N)
ab = a*b
for i in range(int(gcd/ab)):
    
    if S[i*a]!=T[i*b]:
        print(-1)
        exit()
print(gcd)

Solution (Python):


import sys
import itertools
import math

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

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

    if N < M:
        t = M
        M = N
        N = t
        q = S
        S = T
        T = q

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

    ret = -1
    slen = c
    nstep = slen // N
    mstep = slen // M

    dd = gcd(nstep, mstep)
    cc = nstep * mstep // dd

    good = True
    for k in range(0, slen, cc):
        u = (k // nstep) % N
        j = (k // mstep) % M
        if S[u] != T[j]:
            good = False
            break
    if good:
        ret = slen

    
    print("{}".format(ret))


if __name__ == '__main__':
    main()

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

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

def lcm(a, b):
	return int(a * b // gcd (a, b))
answer =lcm(N,M)

G =gcd(N,M)

for k in range(G):
    if S[int(k*N/G)] !=  T[int(k*M/G)]:
        answer =-1

print(answer)

Solution (Python):
a = input().split()
N = int(a[0])
M = int(a[1])
S = list(input())
T = list(input())

if N > M:
    pre = N
    lat = M
else:
    pre = M
    lat = N

while True:
    if pre % lat == 0:
        GCD = int(lat)
        break
    else:
        stp = lat
        lat = pre % lat
        pre = stp

LCM = int(N * M / GCD)

N_l = int(N / GCD)
M_l = int(M / GCD)

ch=0
for i in range(GCD):
    if S[i*N_l] != T[i*M_l]:
        ch = 1
        break

if ch == 0:
    print(LCM)
else:
    print(-1)

Solution (Python):
from fractions import gcd
def lcm(a,b):
    return (a*b)/gcd(a,b)
n,m = map(int, raw_input().split())
s = raw_input() 
t = raw_input()

L = lcm(n,m)
ss = L/n
ts = L/m
seen = {}
works = True

ind = 0
for char in s:
    if ind in seen:
        if not seen[ind] == char:
            works = False
            break
    else:
        seen[ind] = char
    ind += ss

ind = 0
for char in t:
    if ind in seen:
        if not seen[ind] == char:
            works = False
            break
    else:
        seen[ind] = char
    ind += ts

if works: print L
else: print -1

Solution (Python):


import math
import fractions


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


if __name__ == '__main__':
    N, M = map(int, input().split(' '))
    S = input()
    T = input()

    L = lcm(N, M)

    S_index_X = [int(i * L / N) for i in range(N)]
    T_index_X = [int(i * L / M) for i in range(M)]

    common_index = set(S_index_X).intersection(set(T_index_X))
    for i in common_index:
        si = int(i * N / L)
        ti = int(i * M / L)
        if S[si] != T[ti]:
            print(-1)
            exit(0)
    print(L)

Solution (Python):
def Gcd(a, b):
	return Gcd(b, a % b) if b else a

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


p = (N * M) // Gcd(N, M)
re = p

for i in range(0,p,max((p//N),(p//M))):
	
	if i % (p//N) == 0 and i % (p//M) == 0:
		
		if S[i // (p//N)] != T[i // (p//M)]:
			re = -1
			break
print(re)

Solution (Python):
qqq,qqq2 = list(map(int,input().split()))

x = input()
y = input()

if len(x) < len(y):
	x, y = y, x

lx = len(x)
ly = len(y)
lxy = lx * ly
r = lx % ly
while r != 0:
	lx = ly
	ly = r
	r = lx % ly

lcm = int(lxy / ly)
ret = lcm

lx = len(x)
ly = len(y)
stepX = int(lcm / lx)
stepY = int(lcm / ly)

dic = {}
i = 0
for s in x:
	dic[i] = s
	i = i + stepX

i = 0
for s in y:
	if i in dic:
		if dic[i] != s:
			ret = -1
			break
	i = i + stepY

print(ret)

Solution (Python):
import fractions

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

gcd = fractions.gcd(N,M)
if N >= M:
    high = N
    high_s = S
    high_r = N//gcd
    low = M
    low_s = T
    low_r = M//gcd
else:
    high = M
    high_s = T
    high_r = M//gcd
    low = N
    low_s = S
    low_r = N//gcd

cnt = low // low_r
ans = high * low_r
for i in range(0,cnt):
    high_c = high_s[ i * high_r ]
    low_c = low_s[ i * low_r ]
    if high_c != low_c:
        ans = -1
print(ans)

Solution (Python):
def gcd(a, b):
    if a < b:
        a, b = b, a
    if b == 0:
        return a
    c = a % b
    return gcd(b, c)

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

def cmp(x, y, l):
	if len(x) < len(y):
		x, y = y, x
	lx = int(l/len(x))
	ly = int(l/len(y))
	lc = lcm(lx,ly)
	lt = [i*lc for i in range(int(l/lc))]
	for i in lt:
		if i%lc == 0 and x[int(i/lx)] != y[int(i/ly)]:
			return False
	return True

def cmp2(x, y, l):
	if len(x) < len(y):
		x, y = y, x
	lx = int(l/len(x))
	ly = int(l/len(y))
	for i in range(l):
		if i%lx == 0 and i%ly == 0 and x[int(i/lx)] != y[int(i/ly)]:
			return False
	return True


if __name__ == '__main__':
	N, M = list(map(int, input().split()))
	S = input()
	T = input()
	L = lcm(N,M)
	if not cmp(S,T,L):
		print(-1)
	else:
		print(L)

Solution (Python):

from sys import stdin

def Euclid(a,b):
    m = max(a,b)
    n = min(a,b)
    if m == n:
        return m
    else:
        return Euclid(n, m-n)

N, M = [int(x) for x in stdin.readline().rstrip().split()]
S = stdin.readline().rstrip()
T = stdin.readline().rstrip()
euc = Euclid(N,M)

if S[::N//euc] == T[::M//euc]:
    print((N * M) // euc)
else:
    print(-1)

Solution (Python):

import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(10000)


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


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


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


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


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


@mt
def slv(N, M, S, T):
    if N < M:
        S, T = T, S
        N, M = M, N

    if gcd(N, M) == 1:
        if S[0] != T[0]:
            return -1
        return N * M

    else:
        c = gcd(N, M)
        ans = lcm(N, M)
        for i in range(0, ans, ans//c):
            j = i // (M//c)
            k = i // (N//c)
            error_print(i, j, k)
            if S[j] != T[k]:
                return -1
        return lcm(N, M)


def main():
    N, M = read_int_n()
    S = read_str()
    T = read_str()
    print(slv(N, M, S, T))


if __name__ == '__main__':
    main()

Solution (Python):

import fractions
def lcm(x, y):
    return (x * y) // fractions.gcd(x, y)
n,m = map(int,input().split())
s=input()
t=input()
lcm = lcm(n,m)
a = int(lcm/n)
b = int(lcm/m)
for i in range(fractions.gcd(n,m)):
    if s[i*b]==t[i*a]:
        pass
    else:
        print (-1)
        exit()
print (lcm)

Solution (Python):
import math

n,m = map(int, input().split())
s = input()
t = input()
g = 1
div = []
for i in range(2,min(n,m)+1):
    if min(n,m)%i == 0:
        div.append(i)
for i in div:
    if max(n,m)%i == 0:
        g = i
G = g*(n/g)*(m/g)

ans = int(G)
i = 0
while (G/m)*i <= n-1:
    if s[int((G/m)*i)] == t[int((G/n)*i)]:
        pass
    else:
        ans = -1
        break
    i += 1
print(ans)

Solution (Python):
n, m = map(int, input().split())
listS= list(input())
listT = list(input())


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


l = n*m // gcd(n, m)
a = l//n
b = l//m

if listS[0]!=listT[0]:
    print(-1)
else:
    checkI = a*b // gcd(a, b)
    if checkI > l:
        print(l)
    else:
        index=0
        flag=0
        while index < l//min(a, b):
            if index*checkI//a > len(listS)-1 or index*checkI//b > len(listT)-1:
                break
            elif listS[index*checkI//a] != listT[index*checkI//b]:
                print(-1)
                flag=1
                break
            else:
                index+=1
        if flag==0:
            print(l)

Solution (Python):


def gcd(a,b):
    """Compute the greatest common divisor of a and b"""
    while b > 0:
        a, b = b, a % b
    return a

def lcm(a, b):
    """Compute the lowest common multiple of a and b"""
    return a * b / gcd(a, b)


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

    L=int(lcm(N,M))

    N_ = int(L/N)
    M_ = int(L/M)

    L_ = int(lcm(N_,M_))

    for i in range(0,L,L_):
        if(S[int(i/N_)] != T[int(i/M_)]):
            print(-1)
            return 0;

    print(L)
    return 0;

main()

Solution (Python):
import fractions

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

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

nagasa=lcm(N, M)

aidaS=nagasa//N
aidaT=nagasa//M


aidaOnajiCheck=lcm(aidaS, aidaT)

jyoken=True



for i in range((nagasa//aidaOnajiCheck)):
  
  if(not (S[(aidaOnajiCheck//aidaS)*i]==T[(aidaOnajiCheck//aidaT)*i])):
    jyoken=False

if(jyoken):
  print(nagasa)
else:
  print(-1)

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

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


g = gcd(N,M)
l = N*(M//g)
dic = {}
for i in range(N):
    dic[i*(l//N)] = S[i]
for i in range(M):
    if (i*(l//M)) in dic:
        if dic[i*(l//M)] != T[i]:
            print(-1)
            exit(0)

print(l)

Solution (Python):
def gcd(a, b):
    if a < b:
        a, b = b, a
    if b == 0:
        return a
    c = a % b
    return gcd(b, c)

def main():
    N, M = map(int, input().split())
    S = input()
    T = input()
    result = N * M / gcd(N, M)
    cand = (result / N) * (result / M) / gcd(int((result / N)), int((result / M)))
    for i in range(0, int(result / cand)):
        if S[int((i * cand) / (result / N))] != T[int((i * cand) / (result / M))]:
            return '-1'
    return int(result)
print(main())

Solution (Python):
N,M = list(map(int,input().split()))
S = input()
T = input()
sl = list(S)
tl = list(T)
def gcd(a, b):
	while b:
		a, b = b, a % b
	return a
def lcm(x, y):
    return int((x * y) / gcd(x, y))

lcm = lcm(N,M)
Sd = int(lcm/N)
St = int(lcm/M)
kaisu = min(int((N-1)/St),int((M-1)/Sd))
flag = 0
for i in range(kaisu+1):
    if sl[St*i] != tl[Sd*i]:
        flag = 1
if flag == 0:
    print(lcm)
else:
    print(-1)

Solution (Python):
def LCM(a, b):
    tmp = a * b
    while b != 0:
        a, b = b, a % b
    return tmp // a

N, M = map(int, input().split())
s = input()
t = input()
n = LCM(N, M)
a = n // N
b = n // M
for i in range(min((N - 1) // b, (M - 1) // a) + 1):
    if s[b * i] != t[a * i]:
        print("-1")
        break

else:
    print(n)

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


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


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


ans = int(lcm(N, M))


L_N = int(ans / N)

N_M = int(ans / M)

S_list = []
for i in range(1, ans+1, L_N):
    S_list.append(i)

T_list = []
for i in range(1, ans+1, N_M):
    T_list.append(i)

intersect = set(T_list) & set(S_list)

S_in = [x for x, y in enumerate(S_list) if y in intersect]
T_in = [x for x, y in enumerate(T_list) if y in intersect]

flg = True
for x, y in zip(S_in, T_in):
    if S[x] == T[y]:
        continue
    else:
        flg = False

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

Solution (Python):
n, m = list(map(int, input().split(" ")))
s = input()
t = input()
def gcd(a,b):
  while b > 0:
    a, b = b, a % b
  return a
d = gcd(n, m)
l = n*m // d
res = l

s_sep = n//d
t_sep = m//d

for si,ti in zip(s[::s_sep], t[::t_sep]):
  if si!=ti:
    res = -1
    break
print(res)

Solution (Python):

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

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

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

gcdNM = gcd(N, M)
lcmNM = lcm(N, M)

isGood = True
for i in range(gcdNM):
    if S[i * N // (gcdNM)] != T[i * M // (gcdNM)]:
        isGood = False
        break

if isGood and T[0] == S[0]:
    print(lcmNM)
else:
    print(-1)

Solution (Python):

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

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

if S[0] != T[0]:
    print(-1)
    exit(0)
if S == T:
    print(N)
    exit(0)

L = lcm(N,M)
p = L//N
q = L//M
U = ""
k = 0

if gcd(M,N) > 1:
    for k in range(1,L):
        if k%p == 0 and k%q == 0:
            if S[k//p] != T[k//q]:
                print(-1)
                exit(0)
    print(L)
else:
    print(L)

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

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

sl, tl = map(int, input().split())
s = input()
t = input()

m = lcm(sl,tl)

mps = m // sl
mpt = m // tl

tmp = 0
width = max(mps,mpt)
ans = True

while tmp < m:
    if tmp % mps == 0 and tmp % mpt == 0:
        if s[tmp//mps] != t[tmp//mpt]:
            ans = False
            break
    tmp += width

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

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

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

    key = lcm(N, M)
    n = key // N
    m = key // M
    n_list = []
    for i in range(0, key, n):
        n_list.append(i)
    m_list = []
    for j in range(0, key, m):
        m_list.append(j)

    
    i = 0
    j = 0
    while True:
        if i >= len(n_list) or j >= len(m_list):
            break
        if i >= len(S) or j >= len(T):
            break
        if n_list[i] == m_list[j]:
            if S[i] != T[j]:
                print(-1)
                return 0
        if n_list[i] > m_list[j]:
            j += 1
        elif n_list[i] < m_list[j]:
            i += 1
        else:
            i += 1
            j += 1
    print(key)

AGC028A()

Solution (Python):
[m,n] = list(map(int, input().split()))
s = input()
t = input()
ans = -1

for i in range(m):
	if m%(i+1) == 0 and n%(i+1) ==0:
		gcd = i+1

m1 = m//gcd
n1 = n//gcd

flag = 1
for i in range(gcd):
	if s[i*m1]!=t[i*n1]:
		flag = 0
	
	
if flag == 1:
	ans = m*n//gcd

print(ans)

Solution (Python):
import sys
Input = sys.stdin.readline

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

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

l = lcm(N, M)
s = S[0:N:l//M]
t = T[0:M:l//N]

if all(map(lambda a: a[0] == a[1], zip(s, t))):
    print(l)
else:
    print(-1)

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

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

if S[0]!=T[0]:
    print(-1)
else:
    if N==M:
        print(int(N*M)) if S==T else print(-1)
    else:
        g = gcd(N, M)
        if g==1:
            print(int(N*M))
        else:
            flag = False
            s, t = N//g, M//g
            ss = list(map(lambda x: int(x*s), list(range(0,g))))
            tt = list(map(lambda x: int(x*t), list(range(0,g))))
            for i,j in zip(ss,tt):
                if S[i]!=T[j]:
                    flag = True
            if flag:
                print(-1)
            else:
                print(int(s*t*g))

Solution (Python):
def gcd(x,y):
    while y:
        x,y = y,x%y
    return x

n,m = map(int,input().split())
nl = list(input())
ml = list(input())
lcm = n * m // gcd(n,m)
if gcd(n,m) == 1:
    if nl[0] == ml[0]:
        print(lcm)
    else:
        print(-1)
else:
    if nl[::n//gcd(n,m)] == ml[::m//gcd(n,m)]:
        print(lcm)
    else:
        print(-1)

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

n,m = map(int,input().split())
a = gcd(n,m)
b = (n*m)//a


s = input()
t = input()
ans = b

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

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

if N>=M:
	x=N
	y=M
else:
	x=M
	y=N
while y!=0:
	a=y
	y=x%y
	x=a
G=x


L = (N*M)//G
cycle = L//G

flag=0

if G==1: 
	if S[0]==T[0]: print(L)
	else: print("-1")
else:
	for i in range(G):
		if S[cycle*i*N//L]!=T[cycle*i*M//L]:
			flag=1
			break
	if flag==0: print(L)
	else: print("-1")

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


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


k = n * m // gcd(n, m)


for i in range(k, n * m + 1, k):
    g = i * i // n // m // gcd(i // n, i // m)
    flag = True
    for c in range(0, i, g):
        if S[c * n // i] != T[c * m // i]:
            flag = False
            break
    if flag:
        print(i)
        exit()
print(-1)

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

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

gcd_ = gcd(n,m)
lcm = n*m//gcd_

a = lcm//n
b = lcm//m

flag=0
le = min(n,m)//(min(n,m)//gcd_)

for i in range(le):
    if s[i*b]!=t[i*a]:
        flag=1

if flag==1:
    print(-1)
else:
    print(lcm)

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

n,m=map(int,input().split())
s=input()
t=input()
cnt=1
i=0
flag=0

l=int(n*m/gcd(n,m))

r=l/m

while cnt<n:
  if s[int(i*l/m)]==t[int(i*l/n)]:
    flag=1
    cnt+=r
    i+=1
  else:
    flag=0
    break

if flag==1:
  print(l)
else:
  print(-1)

Solution (Python):

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

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

re = -1
if S == T:
    re = N
elif S[0] == T[0]:
    min_num = (N * M)  // gcd(N, M) 
    re = min_num
    
    s_d = min_num // N
    t_d = min_num // M
    
    st_min = (s_d * t_d) // gcd(s_d, t_d)
    st = st_min
    i = 1
    while st // s_d < N and st // t_d < M:
        if S[st // s_d] != T[st // t_d]:
            re = -1
            break
        else:
            i += 1
            st = st_min * i

print(re)

Solution (Python):
from fractions import gcd

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

lcm = N * M // gcd(N, M)
min_s = min((N, M))
S_ = S[::lcm//M]
T_ = T[::lcm//N]

if S_ == T_:
    print(lcm)
else:
    print(-1)

Solution (Python):
from fractions import gcd

n, m = [int(i) for i in input().split()]
S = input()
T = input()

g = n * m // gcd(n, m)

SA = set()
SB = set()

for i in range(0, g, g//n):
    SA.add(i)

for i in range(0, g, g//m):
    SB.add(i)

SC = SA & SB

for s in SC:
    if S[s//(g//n)] != T[s//(g//m)]:
        print(-1)
        exit()

print(g)

Solution (Python):
def GCD(a, b):
	if b > a:
		tmp = a
		a = b
		b = tmp
	if a % b == 0:
		return b
	return GCD(b, a % b)

def LCM(a, b):
	return a * b / GCD(a, b)

def judge():
	N, M = map(int, raw_input().split())
	S = raw_input()
	T =raw_input()
	L = LCM(N, M)
	S_pos = [0] * N
	T_pos = [0] * M
	for i in range(N):
		S_pos[i] = i * L/N
	for i in range(M):
		T_pos[i] = i * L/M
	i = 0
	j = 0
	while i < N and j < M:
		if S_pos[i] == T_pos[j]:
			if S[i] != T[j]:
				return -1
			i += 1
			j += 1
		elif S_pos[i] < T_pos[j]:
			i += 1
		else:
			j += 1
	return L

print judge()

Solution (Python):
def gcb(A, B):
    while B != 0:
        A, B = B, A%B
    return A

N, M = map(int, input().split())
S = input()
T = input()
can = True
agc = N // gcb(N, M) * M
L_N = agc // N
L_M = agc // M
i = 0
while i*L_M < N and i*L_N < M:
    if S[i*L_M] != T[i*L_N]:
        can = False
        break
    i += 1

if can:
    print(agc)
else:
    print(-1)

Solution (Python):
import fractions
a = list(map(int,input().split()))

b = list(input())

c = list(input())

d = fractions.gcd(a[0],a[1])
d = (a[0] * a[1])//d

l = d //a[0]
ll = d//a[1]
lll = (l*ll)//fractions.gcd(l,ll)
p = 0
for i in range(1,d+1,lll):
    if i == 1:
        if b[0] != c[0]:
            p = 1
            break
    else:
        if b[(i-1) //l] != c[(i-1) // ll]:
            p = 1
            break


if p == 0:
    if d != max(a):
        print(d)
    else:
        print(-1)
else:
    print(-1)

Solution (Python):

from fractions import gcd

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


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

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

i = 0

while True:
  i += 1
  L = i*lcm(N, M)
  N_list = [(L//N)*k + 1 for k in range(N)]
  M_list = [(L//M)*k + 1 for k in range(M)]

  
  

  memo = {}

  for idx, n in enumerate(N_list):
    memo[n] = S[idx]

  for idx, m in enumerate(M_list):
    if m in memo.keys():
      if memo[m] != T[idx]:
        break
  else:
    print(L)
    exit(0)

  
  break

print(-1)

Solution (Python):
import fractions

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

S=list(input())
T=list(input())

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

NM=lcm(N,M)



battingS=[]
battingT=[]

for i in range(0,N,NM//M):
  battingS.append(S[i])
  
  

Tcount=0

for j in range(0,M,NM//N):
  battingT.append(T[j])
  
  '''
  if array[j]!=0 and array[j]!=T[Tcount]:
    print(-1)
    exit()
  else:
    array[j]=T[Tcount]
    Tcount+=1
  
  '''

for i in range(len(battingS)):
  if battingS[i]!=battingT[i]:
    print(-1)
    exit()

print(NM)

Solution (Python):
import fractions

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

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

a = l // n
b = l // m

for i in range(0, l, a*b):
    if s[i // a] != t[i // b]:
        print(-1)
        break
else:
    print(l)

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

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

div = gcd(n,m)
length = div * (n//div) * (m//div)

difs = length // n
dift = length // m


g = gcd(difs,dift)
gd = g * (difs//g) * (dift//g)
moves = gd//difs
movet = gd//dift

check = True
i = 0
k = 0

while i < n and k < m and check:
    if s[i] != t[k]:
        check = False
    i += moves
    k += movet
if check:
    print(length)
else:
    print('-1')

Solution (Python):
N,M=map(int,input().split())
S=input()
T=input()
import fractions
gcd=int(N*M/fractions.gcd(N,M))
lis=[int(gcd/N),int(gcd/M)]
for i in range(int(N*M/gcd)):
    if S[int(i*lis[1])]!=T[int(i*lis[0])]:
        print(-1)
        exit()
print(gcd)

Solution (Python):

from fractions import gcd
from bisect import bisect_left
def inpl(): return list(map(int, input().split()))
N, M = inpl()

S = input()
T = input()

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

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

a = G//N
b = G//M

X = [a*i for i in range(N)]
Y = [b*j for j in range(M)]

for i, x in enumerate(X):
    j = bisect_left(Y, x)
    if j < M and Y[j] == x:
        if S[i] != T[j]:
            print(-1)
            break
else:
    print(G)

Solution (Python):
def gcd(a, b):
    if a < b:
        a, b = b, a
    if b == 0:
        return a
    c = a % b
    return gcd(b, c)

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


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

L = lcm(N, M)
D = lcm(L // M, L // N)

for i in range(0, L, D):
    if S[i // (L // N)] != T[i // (L // M)]:
        print("-1")
        exit()
else:
    print(L)

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

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

gcd = gcd(n, m)
L = int(n * m / gcd)

a = int(L/n)
b = int(L/m)

flag=True

if n > m:
    for j in range(n):
        i = j * a
        if (int(i%a) == 0 and int(i%b) == 0):
            if not S[int(i/a)] == T[int(i/b)]:
                flag = False
else:
    for j in range(m):
        i = j * b
        if (int(i%a) == 0 and int(i%b) == 0):
            if not S[int(i/a)] == T[int(i/b)]:
                flag = False
                
if flag:
    print(L)
else:
    print("-1")

Solution (Python):
from sys import stdin
il = lambda func=int: list(map(func, stdin.readline().rstrip().split()))
ils = lambda n, s="int(input())": [eval(s) for _ in range(n)]
def gcd(a, b):
    if a < b: return gcd(b, a)
    if b == 0: return a
    return gcd(b, a%b)
def lcm(a, b):
    return a * b // gcd(a, b)

n, m = il()
s = input()
t = input()
aa = gcd(n, m)
bb = lcm(n, m)
cc = aa // bb
for i in range(aa):
    if s[n//aa*i] != t[m//aa*i]:
        print(-1)
        exit()
print(bb)

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

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

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

lcm = lcmCalc(n, m)





flg = 0
for i in range(n):
	index = i * lcm // n + 1
	if (index - 1) % (lcm // m) == 0:
		j = (index - 1) // (lcm // m)
		if s[i] != t[j]:
			print("-1")
			flg = 1
			break
if flg == 0:
	print(lcm)

Solution (Python):
(n, m) = map(int, input().split())

def kouyaku(n, m):
    a = n % m
    if a == 0:
        return m
    return kouyaku(m, a)

s = input()
t = input()

a = kouyaku(n, m)

sn = n // a
sm = m // a

ok = True
for i in range(a):
    if(s[i*sn] != t[i*sm]):
        print(str(-1))
        ok = False
        break

if ok == True:
    print(sn*sm*a)

Solution (Python):
def gcd(x, y):
    while y > 0:
        x, y = y, x%y
    return x

n, m = map(int, input().split())
S = input()
T = input()
L = (n*m) // gcd(n, m)
c = 0

xs = L//n
xt = L//m
step = xs * xt

for i in range(0, L, step):
    if S[i//xs] != T[i//xt]:
        print(-1)
        exit()
print(L)

Solution (Python):

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

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

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

l = lcm(n,m)

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

Solution (Python):
import fractions


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

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

span = fractions.gcd(n, m)
for i in range(span):
    if s[int(n/span)*i] != t[int(m/span)*i]:
        print("-1")
        exit()
print(lcm(n, m))

Solution (Python):
import math


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

if N>M:
    N,M = M,N
    S,T = T,S
    
def gcd(a, b):
    while b:
	    a, b = b, a % b
    return a
    
L = int(M*N/gcd(N, M))

for i in range(N):
    if (M*i)%N == 0:
        j = int((M*i)/N)
        if S[i] != T[j]:
            print(-1)
            exit(0)

print(L)

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

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

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

g = lcm(n,m)

if n < m:
    sm = n
    bi = m
    ls = s
    bs = t
else:
    sm = m
    bi = n
    ls = t
    bs = s
a = g//sm
b = g//bi
flg = False
for i in range(sm):
    p = i * a
    if p % b == 0:
        if bs[p//b] != ls[i]:
            flg = True
            break
if flg:
    print(-1)
else:
    print(g)

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

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



def mas():
    n,m = map(int,input().split())
    s = list(input())
    t = list(input())


    length = lcm(n,m)
    stepn = length//n
    stepm = length//m
    step_lcm = lcm(stepn,stepm)

    if s[0] != t[0]:
        print(-1)
        return 0
    else:
        if step_lcm >= length:
            print(length)
            return 0
        else:
            steps = step_lcm//stepn
            stept = step_lcm//stepm

            pos_s = 0
            pos_t = 0
            i = 0
            pos_s = 0
            pos_t = 0
            while pos_s < n and pos_t < m:
                if not s[pos_s] == t[pos_t]:
                    print(-1)
                    return 0
                i+=1
                pos_s = i*steps
                pos_t = i*stept
            print(length)

mas()

Solution (Python):
import sys
N, M = [int(i) for i in input().split(' ')]
S, = [i for i in input().split(' ')]
T, = [i for i in input().split(' ')]
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

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

if S[0] != T[0]:
    print(-1)
else:
    x = lcm(N,M)
    a = x // N
    b = x // M
    c = lcm(a, b)
    ii = 1
    while ii * c + 1 <= x:


        if S[ii * (c//a) ] != T[ii * (c//b) ]:
            print(-1)
            sys.exit()
        ii += 1
    print(x)

Solution (Python):
import fractions

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

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

flag = True
for i in range(L):
    if (S[N//L * i] != T[M//L * i]):
        flag = False

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

Solution (Python):
def gcd(N,M):
    while True:
        if min(N,M)==0:
            return max(N,M)
        elif N>=M:
            N%=M
        elif M>N:
            M%=N
def lcm(N,M):
    return N*M//gcd(N,M)

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

L=lcm(N,M)

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

Solution (Python):
def main():
    n, m = map(int,input().split())
    s = input()
    t = input()

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

    nlist = [0 for i in range(n)]
    mlist = [0 for i in range(m)]
    for i in range(n):
        nlist[i] =  i*l//n

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

    src_set = set(nlist)
    tag_set = set(mlist)
    matched_list = list(src_set.intersection(tag_set))

    for i in matched_list:
        s_index = nlist.index(i)
        t_index = mlist.index(i)

        if s[s_index] != t[t_index]:
            print("-1")
            exit()

    print(l)

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

if __name__ == "__main__":
        main()