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):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(str, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10**9 + 7


N, M = MAP()

S = input()
T = input()

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

G = gcd(N, M)

n = N//G
m = M//G

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

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

from fractions import gcd

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

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

ans=lcm

dn={}
for i in range(n):
    if i==0:
        dn[1]=s[i]
    else:
        dn[i*int((lcm)/n) +1]=s[i]

for j in range(m):
    if j==0:
        continue
    else:
        k = j*int(lcm/m) + 1

        if k in dn:
            if dn[k]!=t[j]:
                ans=-1
        else:
            dn[k]=t[j]

print(ans)

Solution (Python):
import math,itertools,fractions,heapq,collections,bisect,sys,queue,copy

sys.setrecursionlimit(10**7)
inf=10**20
mod=10**9+7
dd=[(-1,0),(0,1),(1,0),(0,-1)]
ddn=[(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return [int(x) for x in sys.stdin.readline().split()]

def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return input()


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



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


def main():
  n,m=LI()
  s=S()
  t=S()
  a=lcm(n,m)

  x={}
  for i in range(n):
    x[i*(a//n)]=s[i]

  

  for i in range(m):
    if i*(a//m) in x:
      if t[i]!=x[i*(a//m)]:
        return -1

  return a


print(main())

Solution (Python):





import math
import fractions
import sys
import bisect
import heapq  
import collections
from collections import deque
import pprint

inf = 10**18
mod = 10**9+7

n,m = map(int, input().split())
s = input()
t = input()
f=fractions.gcd(n,m)           
f2=n*m//f                          


x = f2//n
y = f2//m

for i in range(n):
    if (x*i)%y==0:
        if s[i] != t[x*i//y]:
            print(-1)
            sys.exit()
print(f2)

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


def my_lcm(a, b):
    cum = a * b
    if a > b:
        a, b = b, a
    while a != 0:
        a, b = b % a, a
    
    return cum // b


ans = my_lcm(n, m)
s_idx = 0
t_idx = 0
while s_idx < n and t_idx < m:
    if s[s_idx] != t[t_idx]:
        print(-1)
        exit()
    else:
        a = s[s_idx] + t[t_idx]
        t_idx += ans // n
        s_idx += ans // m
print(ans)

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()
L = gcd(n,m)
ans = lcm(n,m)
for i in range(L):
    if not s[n//L*i] == t[m//L*i]:
        ans = -1
        break
print(ans)

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

Solution (Python):



from fractions import gcd   


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

def main():
    N, M = map(int, input().split())
    S = input()
    T = input()
    L = lcm(N,M)
    if S[::L//M]==T[::L//N]:
        print(L)
    else:
        print(-1)

if __name__ == '__main__':
    main()

Solution (Python):
from fractions import gcd
N, M = map(int, input().split())
S = input()
T = input()
flg = True

ans = N*M//gcd(N, M)
n = ans // N
m = ans // M
a = n*m//gcd(n, m)
nn = a // n
mm = a // m
for i in range(1, ans//a):
    if S[nn*i] != T[mm*i]:
        flg = False
if S[0] != T[0]:
    flg = False
if flg:
    print(ans)
else:
    print(-1)

Solution (Python):
import fractions

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

g = fractions.gcd(N,M)

L = g * (N // g) * (M // g)

if S[0::N//g] == T[0::M//g]:
  print(L)
else:
  print(-1)

Solution (Python):
import fractions

def lcm(x,y):
    return (x*y) // fractions.gcd(x, y)
    
x, y = map(int, input().split())
s = input()
t = input()

lc = lcm(x,y)

s_l = lc//x
t_l = lc//y

for i in range(y):
    if i%s_l == 0:
        if t[i] == s[i*t_l//s_l]:
            continue
        else:
            print(-1)
            break
else:
    print(lc)

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

Solution (Python):
import fractions

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

if N == M:
    print(N if S == T else -1)
else:
    G = fractions.gcd(N, M)
    L = N * M // G
    n = N // G
    m = M // G
    ans = True
    for k in range(G):
        if S[k * n] != T[k * m]:
            ans = False
            break
    print(L if ans else -1)

Solution (Python):
from fractions 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 = True
for k in range(G):
    if S[k*n] != T[k*m]:
        ans = False
        break
print(L if ans else -1)

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache






MOD = 10**9+7
INF = float('inf')






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)



def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n):
    return kaijo_memo[n]
  if(len(kaijo_memo) == 0):
    kaijo_memo.append(1)
  while(len(kaijo_memo) <= n):
    kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n):
    return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0):
    gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n):
    gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if(n == r):
    return 1
  if(n < r or r < 0):
    return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1:
    arr.append([temp, 1])
  if arr==[]:
    arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


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


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


def count_bit(n):
  count = 0
  while n:
    n &= n -1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n:
    return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count




N,M = IL()
S1 = S()
S2 = S()

GCD = gcd(N,M)
LCM = lcm(N,M)

for i in range(GCD):
  if S1[i*N//GCD] != S2[i*M//GCD]:
    print(-1)
    exit()
print(LCM)

Solution (Python):
from fractions 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 = True
for k in range(G):
    if S[k * n] != T[k * m]:
        ans = False
        break
print(L if ans else -1)

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

l = lcm(n,m)
i = 0
j = 0
ans = l
while i < n or j < m:
    temp_n = i*l//n+1
    temp_m = j*l//m+1
    if temp_n == temp_m:
        if S[i] != T[j]:
            ans = -1
            break
        i += 1
        j += 1
    elif temp_m > temp_n:
        i += 1
    else:
        j += 1

print(ans)

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

cfac = fractions.gcd(N,M)

B = N//cfac
C = M//cfac
 
i = 0
for i in range(cfac):
  if S[i*B] != T[i*C]:
    print(-1)
    exit()
    
print(cfac*B*C)

Solution (Python):


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

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

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

l = lcm(n, m)
d = gcd(n, m)
n //= d
m //= d

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

Solution (Python):
import sys
import fractions

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N, M = [int(x) for x in input().split()]
    S = input().strip()
    T = input().strip()

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

    dic = {}
    for i, s in enumerate(S):
        dic[(ans // N) * i + 1] = s

    for i, t in enumerate(T):
        if ((ans // M) * i + 1) in dic.keys():
            if dic[(ans // M) * i + 1] != t:
                print(-1)
                return

    print(ans)


if __name__ == '__main__':
    main()

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

flag=True
import fractions
gcdnm=fractions.gcd(n,m)
lcmnm=(n*m)//gcdnm

nn=n//gcdnm
mm=m//gcdnm

for i in range(gcdnm):
    if S[i*nn]!=T[i*mm]:
        flag=False

if flag==True:
    print(lcmnm)
else:
    print(-1)

Solution (Python):
import sys
from fractions import gcd

input = sys.stdin.readline


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


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

    L = lcm(N, M)
    n = L // N
    m = L // M

    ans = L
    i = 0
    while i < L // (n * m):
        if S[m * i] != T[n * i]:
            ans = -1
            break
        i += 1

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import fractions

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


l = (N * M) // fractions.gcd(N, M)

ans = {1: S[0]}
for i in range(1, N):
    c_num = i*l//N+1
    ans[c_num] = S[i]

for i in range(M):
    if i == 1:
        if ans[1] != T[0]:
            print(-1)
            exit(0)

    c_num = i*l//M+1
    if c_num in ans:
        if ans[c_num] != T[i]:
            print(-1)
            exit(0)
    else:
        ans[c_num] = T[i]
print(l)

Solution (Python):
from fractions import gcd

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

gcd_nm = gcd(n, m)
ans = n * m // gcd_nm
n_tmp = n // gcd_nm
m_tmp = m // gcd_nm
for i in range(gcd_nm):
    if s[i * n_tmp] != t[i * m_tmp]:
        print(-1)
        break
else:
    print(ans)

Solution (Python):
from fractions import gcd
n, m = map(int, input().split())
s = input()
t = input()
gcm = gcd(n, m)
lcm = n * m // gcm
for i in range(gcm):
    if s[(n // gcm) * i] != t[(m // gcm) * i]:
        print(-1)
        exit()
print(lcm)

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

import sys

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


g = gcd(N, M)
sn = N//g
sm = M//g

ok = True
for k in range(0, g):
    a = k * sn
    b = k * sm
    if S[a] != T[b]:
        ok = False
        break

if ok:
    print(N*M//g)
else:
    print(-1)

Solution (Python):
def main():
    import sys
    from collections import defaultdict
    sys.setrecursionlimit(10**6)
    input = sys.stdin.readline

    def gcd(a, b):
        if b == 0:
            return a
        return gcd(b, a % b)
    
    N, M = [int(x) for x in input().strip().split()]
    S = input().strip()
    T = input().strip()
    L = (N * M) // gcd(N, M)
    d = defaultdict(int)
    for n in range(N):
        d[L//N*n] = S[n]
    for m in range(M):
        if d[L//M*m] == 0 or d[L//M*m] == T[m]:
            continue
        else:
            print(-1)
            return
    print(L)

if __name__ == '__main__':
    main()

Solution (Python):
from fractions import gcd


N, M = map(int, input().split())
S = input()
T = input()
g = gcd(N, M)
N //= g
M //= g
for i in range(g):
    if S[i * N] != T[i * M]:
        print(-1)
        break
else:
    print(N * M * g)

Solution (Python):
from fractions import gcd


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


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

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

Solution (Python):
from fractions import gcd


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


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

L = lcm(N, M)
X = {}

for i in range(N):
    X[(L // N) * i] = S[i]

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

Solution (Python):
def ii():return int(input())
def iim():return map(int,input().split())
def iil():return list(map(int,input().split()))

from fractions import gcd
n,m = iim()
s = input()
t = input()
num = gcd(n,m)
lcm = n*m//num
print(lcm if s[::n//num] == t[::m//num] else -1)

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

def gcd(v1, v2):
    if v2 == 0:
        return v1
    return gcd(v2, v1%v2)

def lcm(v1,v2):
    return v1 * v2 // gcd(v1,v2)

my_gcd = gcd(N,M)
s_ = S[::N//my_gcd]
t_ = T[::M//my_gcd]
if s_ == t_:
    print(lcm(N,M))
else:
    print(-1)

Solution (Python):
from fractions import gcd
def main():
    n, m = list(map(int, input().split()))
    s = list(input())
    t = list(input())
    lcm = n * m // gcd(n, m)
    a, b = lcm // n, lcm // m
    lcmx = a * b // gcd(a, b)
    for i in range(lcm // lcmx):
        if s[i * b] != t[i * a]:
            print(-1)
            break
    else:
        print(lcm)

if __name__ == '__main__':
    main()

Solution (Python):
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()

ans = lcm(n, m)

chk = {}

for i in range(n):
    d = ans//n
    chk[i*d] = s[i]
for i in range(m):
    d = ans//m
    if i*d in chk and chk[i*d] != t[i]:
        print(-1)
        exit()
print(ans)

Solution (Python):
from fractions import gcd
N,M=map(int,input().split())
S=input()
T=input()
l=gcd(N,M)
print(N*M//l if all(S[i*N//l]==T[i*M//l] for i in range(l)) else "-1")

Solution (Python):
from fractions import gcd
n,m = [int(x) for x in input().split()]
s = input()
t = input()

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

ans = f(n,m)

if s[::ans//m] == t[::ans//n]:
    print(ans)
else:
    print(-1)

Solution (Python):
def f(a,b):
    if b:
        return f(b,a%b)
    return a
n,m=map(int,input().split())
s=input()
t=input()
a=f(n,m)
print(n//a*m if s[::n//a]==t[::m//a] else -1)

Solution (Python):
n,m=map(int,input().split())
s=str(input())
s=list(s)
t=str(input())
t=list(t)
ans=-1
if s[0]==t[0]:
  import fractions
  temp=len(s)*len(t)//fractions.gcd(len(s),len(t))
  k=fractions.gcd(len(s),len(t))
  count=1
  for i in range(1,k):
    if s[i*int(len(s)/k)]==t[i*int(len(t)/k)]:
      count=count+1
  if count==k:
    ans=temp
print(ans)

Solution (Python):
def f(a,b):
    if b:
        return f(b,a%b)
    return a
n,m=map(int,input().split())
s=input()
t=input()
a=f(n,m)
print(n//a*m if s[::n//a]==t[::m//a] else -1)

Solution (Python):
from fractions import gcd

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

dic = {}
L = int((N*M) / gcd(N,M))
ans = L

for i in range(N):
  dic[int(i*(L/N)+1)] = i

key = set(dic.keys())
for i in range(M):
  if i*(L/M)+1 in key:
    if S[dic[int(i*(L/M)+1)]] == T[i]:continue
    else: 
      ans = -1
      break

  


print(ans)

Solution (Python):
i=input;n,m=map(int,i().split());g=m-max(a*n%m for a in range(m));print([n*m//g,-1][i()[::n//g]!=i()[::m//g]])

Solution (Python):
i=input;n,m=map(int,i().split());g=m-max(a*n%m for a in range(m));print(i()[::n//g]!=i()[::m//g]and-1or n*m//g)

Solution (Python):

import collections
import itertools as it
import math



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





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

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

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

l = lcm(N, M)

Moji = {}
Moji[0] = S[0]

for i in range(1, N):
    index = i * (l//N) + 1
    Moji[index-1] = S[i]

for i in range(1, M):
    index = i * (l//M) + 1
    if index-1 in Moji and Moji[index-1] != T[i]:
        print(-1)
        exit()

print(l)

Solution (Python):
from fractions import gcd

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

s = input()
t = input()





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

print(n*m//g)

Solution (Python):
from fractions import gcd
N,M=map(int,input().split())
S=input()
T=input()
g=gcd(N,M)
n=N//g
m=M//g
for i in range(g):
    if S[i*n]!=T[i*m]:
        print(-1)
        break
else:
    print(n*m*g)

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

Solution (Python):
ma = lambda :map(int,input().split())
ni = lambda:int(input())
import collections
import math
import fractions
gcd = fractions.gcd
n,m = ma()
s = input()
t = input()
l = m*n //gcd(m,n)
ln = []
for i in range(n):
    ln.append((l//n*i+1,s[i]))

for i in range(m):
    ln.append((l//m*i+1,t[i]))
ln.sort()
prev=-1
wp = ""
for num,w in ln:
    if num==prev:
        if w ==wp:
            pass
        else:
            print(-1)
            exit()
    prev=num
    wp = w
print(l)

Solution (Python):
A,B=list(map(int,input().split()))
l_a=list(input())
l_b=list(input())
import fractions
gcd=fractions.gcd(A,B)
total=A*B//gcd
A_n=total//A
B_n=total//B
S=A_n*B_n//fractions.gcd(A_n,B_n)
for i in range(total//S):
   if l_a[i*B_n] != l_b[i*A_n]:
      print(-1)
      exit()
print(total)

Solution (Python):
import sys
import heapq
import re
from itertools import permutations
from bisect import bisect_left, bisect_right
from collections import Counter, deque
from fractions import gcd
from math import factorial, sqrt, ceil
from functools import lru_cache, reduce
INF = 1 << 60
MOD = 1000000007
sys.setrecursionlimit(10 ** 7)


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def is_prime(n):
    if n == 1:
        return False
    for i in range(2,int(n**0.5)+1):
        if n % i == 0:
            return False
    return True




def warshall_floyd(d, n):
    
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d



def dijkstra_heap(s, edge, n):
    
    d = [10**20] * n
    used = [True] * n 
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr


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


def lcm_list(numbers):
    return reduce(lcm, numbers, 1)


def gcd_list(numbers):
    return reduce(gcd, numbers)






def eratosthenes(limit):
    A = [i for i in range(2, limit+1)]
    P = []

    while True:
        prime = min(A)
        
        if prime > sqrt(limit):
            break
            
        P.append(prime)
            
        i = 0
        while i < len(A):
            if A[i] % prime == 0:
                A.pop(i)
                continue
            i += 1
            
    for a in A:
        P.append(a)
            
    return P


def permutation_with_duplicates(L):

    if L == []:
        return [[]]

    else:
        ret = []

        
        S = sorted(set(L))

        for i in S:

            data = L[:]
            data.remove(i)

            for j in permutation_with_duplicates(data):
                ret.append([i] + j)

        return ret



n, m = map(int, input().split())
s = input()
t = input()
l = lcm(n, m)
yes = True
if n == m and s != t:
    yes = False
elif n > m:
    for i in range(m):
        if i * n / m == int(i * n / m) and t[i] != s[int(i * n / m)]:
            
            yes = False
else:
    for i in range(n):
        if i * m / n == int(i * m / n) and s[i] != t[int(i * m / n)]:
            yes = False
if yes:
    print(l)
else:
    print(-1)

Solution (Python):
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 = str(input())
t = str(input())
g = gcd(n, m)
l = lcm(n, m)
for i in range(g):
    if s[i*n//g] != t[i*m//g]:
        print(-1)
        break
else:
    print(l)

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

def answer(s, t):
    a = len(s)
    b = len(t)
    if s[0] != t[0]:
        return -1
    if a < b:
        temp = a
        a = b
        b = temp
        temp = s
        s = t
        t = temp
    gcdAB = gcd(a, b)
    if gcdAB == 1:
        return a*b
    else:
        stack = 0
        sl = (gcdAB * (a//gcdAB) * (b//gcdAB))
        aJump = sl//a
        bJump = sl//b
        for i in range(b):
            if stack%aJump == 0:
                if s[stack//aJump] != t[i]:
                    return -1
            stack = bJump*(i+1)
        return sl
                

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

Solution (Python):
from fractions import gcd

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

g = gcd(n, m)

print(n * m // g if s[::n // g] == t[::m // g] else -1)

Solution (Python):
from fractions import gcd
N,M=map(int,input().split(' '))
S=input()
T=input()
G=gcd(N,M)
L = N*M//G
ln = list(range(0,L,(N//G)))
lm = list(range(0,L,(M//G)))
for i,j in zip(ln,lm):
    if i>=N or j>=M:
        break
    if S[i] != T[j]:
        print(-1)
        exit()
print(L)

Solution (Python):











import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
from math import floor,sqrt,factorial,hypot,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 fractions import gcd
from random import randint
def ceil(a,b): return (a+b-1)//b
inf=float('inf')
mod = 10**9+7
def pprint(*A): 
    for a in A:     print(*a,sep='\n')
def INT_(n): return int(n)-1
def MI(): return map(int,input().split())
def MF(): return map(float, input().split())
def MI_(): return map(INT_,input().split())
def LI(): return list(MI())
def LI_(): return [int(x) - 1 for x in input().split()]
def LF(): return list(MF())
def LIN(n:int): return [I() for _ in range(n)]
def LLIN(n: int): return [LI() for _ in range(n)]
def LLIN_(n: int): return [LI_() for _ in range(n)]
def LLI(): return [list(map(int, l.split() )) for l in input()]
def I(): return int(input())
def F(): return float(input())
def ST(): return input().replace('\n', '')
def main():
    N,M=MI()
    S=ST()
    T=ST()
    lcm = N*M//(gcd(N,M))
    ans = defaultdict(str)
    for i,s in enumerate(S):
        ans[i*lcm//N] = s
    for i,t in enumerate(T):
        if(ans[i*lcm//M] not in (t,"")):
            print(-1)
            return 
    print(lcm)
if __name__ == '__main__':
    main()

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

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

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

C=N*M//gcd(max(N,M),min(N,M))
n=C//N
m=C//M

i=0
j=0
ans=C
while i<C and j<C:
    if  i==j:
        if S[i//n]!=T[j//m]:
            ans=-1
        i+=n
        j+=m
    elif i<j:
        i+=n
    else:
        j+=m
print(ans)

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

def gcd(num1,num2):
    r=1
    while r!=0:
        r=num1%num2
        num1=num2
        num2=r
    return num1

def lcm(num1,num2):
    return num1*num2//gcd(num1,num2)

g1 = lcm(n,m)
g2 = lcm(g1//n,g1//m)

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

Solution (Python):
from fractions import gcd
n,m=map(int,input().split())
s=input()
t=input()
g=gcd(n,m)
ans=n*m//g
stepn=n//g
stepm=m//g
for i in range(g):
    if s[stepn*i]!=t[stepm*i]:print(-1);exit()
print(ans)

Solution (Python):
from fractions import gcd
N,M = map(int,input().split())
s = input()
t = input()
n = N//gcd(N,M)
m = M//gcd(N,M)
for i in range(gcd(N,M)):
    if s[i*n] == t[i*m]:
        continue
    else:
        print(-1)
        break
else:
    print(N*M//gcd(N,M))

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

G = N * M // fractions.gcd(N, M)
slist = [i*(G//N) for i in range(N)]
mlist = [i*(G//M) for i in range(M)]
sm = set(slist) & set(mlist)
for i in sm:
    si = slist.index(i)
    mi = mlist.index(i)
    if S[si] != T[mi]:
        print(-1)
        exit()

print(G)

Solution (Python):
def make_divisors(n):
    divisors = set()
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.add(i)
            if i != n // i:
                divisors.add(n//i)
    return divisors

N,M = (int(x) for x in input().split())
S = list(input())
T = list(input())
if M > N:
    N,M = M,N
    S,T = T,S
dn = make_divisors(N)
dm = make_divisors(M)
dnm = dn & dm
if dnm == {1}:
    if S[0] == T[0]:
        print(N*M)
    else:
        print('-1')
else:
    gcd = max(dnm)
    n = N // gcd
    m = M // gcd
    for i in range(N//n):
        if S[n*i] != T[m*i]:
            print('-1')
            break
    else:
        print(N*M//gcd)

Solution (Python):
from fractions import gcd
n,m = map(int,input().split())
s = input()
t = input()

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

li = set([i*(len_x//n)+1 for i in range(n)])&set([j*(len_x//m)+1 for j in range(m)])

for l in li:
    if s[(l-1)//(len_x//n)]!=t[(l-1)//(len_x//m)]:
        print(-1);exit()
print(len_x)

Solution (Python):
from fractions import gcd
n,m=map(int,input().split())
s=input()
t=input()
g=gcd(n,m)
l=n*m//g
for i in range(n):
  if i%(n//g)==0 and not s[i]==t[i*m//n]:
    print(-1)
    exit()
print(l)