Harryxun/stf_run huggingface dataset:
import math
def main5():
    N, M = map(int, input().split())
    S = input()
    T = input()

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

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

    print(L)

if __name__ == "__main__":
    main4()

### FIXED CODE ###

import math
def main4():
    N, M = map(int, input().split())
    S = input()
    T = input()

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

    pair = dict()

    for i in range(1, N + 1):
        idx = (i - 1) * (L // N) + 1
        pair[idx] = S[i - 1]

    for i in range(1, M + 1):
        idx = (i - 1) * (L // M) + 1

        if idx in pair.keys():
            if pair[idx] != T[i - 1]:
                print(-1)
                exit()

    print(L)

if __name__ == "__main__":
    main4()
N, M = map(int,input().split())
L = [0] * M
R = [0] * M
for i in range(M):
    L[i], R[i] = map(int,input().split())
ans = 0
A = [0] * N
for i in range(M):
    A[L[i]:R[i]+1] += 1
for i in range(N):
    if A[i] == M:
        ans += 1
print(ans)

### FIXED CODE ###

N, M = map(int,input().split())
L = [0] * M
R = [0] * M
for i in range(M):
    L[i], R[i] = map(int,input().split())
ans = 0
A = [0] * N
L_max = max(L)
R_min = min(R)
if R_min >= L_max:
    ans = R_min - L_max + 1
else:
    ans = 0
print(ans)
a,b,c,d = map(int,input().split())
ans = 0
for i in range(101):
  if a < i < b and c < i < d
  ans += 1
print(ans+1)
  

### FIXED CODE ###

N =list(input())
if N[0] == N[2]:
  print("Yes")
else:
  print("No")
import math
r=int(input())
m=float(math.pi)
s=m*(r**2)
l=(2*r)*m
print(s,l)

### FIXED CODE ###

import math
r=float(input())
m=float(math.pi)
s=r*r*m
l=2*r*m
print(s,l)
def keisan(num):
    x = num
    keisan = x ** 3
    return keisan

if __name__ == '__main__':
    print(keisan(2) + \n)

### FIXED CODE ###

x = raw_input()
print(str(int(x) ** 3))
def flip(N, M, K, Mnum, Nnum, black):
    if black < 0 or black > K:
        return False
    if black == K:
        return True

    return flip(N, M, K, Mnum+1, Nnum, black+M-Nnum) or flip(N, M, K, Mnum, Nnum+1, black+N-Nnum)

if __name__ == '__main__':
    inputs = input('> ').split()
    if flip(int(inputs[0]), int(inputs[1]), int(inputs[2]), 0, 0, 0):
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

N, M, k = tuple(int(i) for i in input().split(' '))
ans = 'No'
for a in range(N + 1):
    for b in range(M + 1):
        if M * a + N * b - 2 * a * b == k:
            ans = 'Yes'
            break
print(ans)
S = input()
ans = "Yes"

for i in range(len(S)):
	if S[i]%2 == 0:
		if !(S[i] in ('R', 'U', 'D')):
			ans = "No"
			break
	
	if S[i]%2 == 1:
		if !(S[i] in ('L', 'U', 'D')):
			ans = "No"
			break
	
print(ans)

### FIXED CODE ###

S = input()
ans = "Yes"

for i in range(len(S)):
	if i%2 == 0:
		if S[i] == 'L':
			ans = "No"
			break
	
	if i%2 == 1:
		if S[i] == 'R':
			ans = "No"
			break
	
print(ans)
from collections import deque

N = int(input())
graph = [[] for _ in range(N)]
for _ in range(N - 1):
    u, v, w = map(int, input().split())
    u, v, w = u - 1, v - 1, w % 2
    graph[u].append([v, w])
    graph[v].append([u, w])

colors = [-1 for _ in range(N)]
stack = deque()
stack.append(0)
colors[0] = 0

while stack:
    n = stack.pop()
    for _next, w in graph[n]:
        if colors[_next] != -1:
            continue
        colors[_next] = (colors[n] + w) % 2
        stack.append([_next])

for c in colors:
    print(c)


### FIXED CODE ###

from collections import deque

N = int(input())
graph = [[] for _ in range(N)]
for _ in range(N - 1):
    u, v, w = map(int, input().split())
    u, v = u - 1, v - 1
    graph[u].append([v, w])
    graph[v].append([u, w])

colors = [-1 for _ in range(N)]
stack = deque()
stack.append(0)
colors[0] = 0

while stack:
    n = stack.popleft()
    for _next, w in graph[n]:
        if colors[_next] != -1:
            continue
        colors[_next] = (colors[n] + w) % 2
        stack.append(_next)

for c in colors:
    print(c)
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
''' 
------------------------
author : iiou16
------------------------
'''
import numpy as np


def main():
    N, K = list(map(int, input().split()))
    H = list(map(int, input().split()))
    H = np.array(H)

    cost = np.array([100000] * N)
    cost[0] = 0
    for i in range(1, N):
        cost[i] = min(
            cost[max(i - K, 0): i] + abs(H[i] - H[max(i - K, 0): i]))
        # print(i, cost[i])
    print(cost[N - 1])


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
''' 
------------------------
author : iiou16
------------------------
'''
import numpy as np


def main():
    N, K = list(map(int, input().split()))
    H = list(map(int, input().split()))
    H = np.array(H)

    cost = np.array([100000] * N)
    cost[0] = 0
    for i in range(1, N):
        cost[i] = min(
            cost[max(i - K, 0): i] + abs(H[i] - H[max(i - K, 0): i]))
        # print(i, cost[i])
    print(cost[N - 1])


if __name__ == '__main__':
    main()
import.math
print (2*(math.pi)*R)


### FIXED CODE ###

import math
a = int(input())
print(2 * a * math.pi)
import sys
INF = 10 ** 9
MOD = 10 ** 9 + 7
from collections import deque
sys.setrecursionlimit(100000000)

fact2 = [0] * 1000011
def cnt2(n):
    if n%2 == 1:
        return 0
    else:
        fact2[n] = 1 + fact2[n//2]
        return fact2[n]

factorial = [0,0]
for i in range(2,1000010):
    factorial.append(factorial[-1] + cnt2(i))

def nck(n,k):
    return factorial[n] - factorial[k] - factorial[n - k]

def nxor(x,n):
    if n > 0:
        return 0
    else:
        return x


def main():
    n = int(input())
    a = [int(i) - 1 for i in list(input())]
    
    cumxor = 0
    amod = [i%2 for i in a]
    for i in range(n):
        cumxor ^= nxor(amod[i],nck(n - 1,i))
    
    if cumxor == 1:
        ans = 1
    else:
        if 1 in a:
            ans = 0
        else:
            cumxor = 0
            adiv = [a//2 for i in a]
            for i in range(n):
                cumxor ^= nxor(adiv[i],nck(n - 1,i))
            if cumxor == 0:
                ans = 0
            else:
                ans = 2
    
    print(ans)

if __name__=='__main__':
    main()

### FIXED CODE ###

import sys
INF = 10 ** 9
MOD = 10 ** 9 + 7
from collections import deque
sys.setrecursionlimit(100000000)

fact2 = [0] * 1000011
def cnt2(n):
    if n%2 == 1:
        return 0
    else:
        fact2[n] = 1 + fact2[n//2]
        return fact2[n]

factorial = [0,0]
for i in range(2,1000010):
    factorial.append(factorial[-1] + cnt2(i))

def nck(n,k):
    return factorial[n] - factorial[k] - factorial[n - k]

def nxor(x,n):
    if n > 0:
        return 0
    else:
        return x


def main():
    n = int(input())
    a = [int(i) - 1 for i in list(input())]
    
    cumxor = 0
    amod = [i%2 for i in a]
    for i in range(n):
        cumxor ^= nxor(amod[i],nck(n - 1,i))
    
    if cumxor == 1:
        ans = 1
    else:
        if 1 in a:
            ans = 0
        else:
            cumxor = 0
            adiv = [i//2 for i in a]
            for i in range(n):
                cumxor ^= nxor(adiv[i],nck(n - 1,i))
            if cumxor == 0:
                ans = 0
            else:
                ans = 2
    
    print(ans)

if __name__=='__main__':
    main()
n = int(input())
if '9' in n:
  print('Yes')
else:
  print('No')
  

### FIXED CODE ###

n = input()
print("Yes" if "9" in n else "No")
from math import factorial as fac
N,M = map( int, input().split() )
break_list = []
for i in range(M):
    break_list.append( int( input() ) )
break_list.append( N + 1 )
start = 0
ans = 1
t = 1
for i in break_list:
    sum_c = 0
    end = i - 1
    if start > end:
        t = -1
    step_1 = end - start
    step_2 = int( ( end - start ) / 2 )
    for j in range(step_2 + 1):
        k = step_1 - 2 * j
        sum_c += fac(k + j) // ( fac(j) * fac(k) )
    ans *= sum_c
    start = i + 1
    
if t == 1:
    print( ans % 1000000007 )
else:
    print(0)

### FIXED CODE ###

N,M = map( int, input().split() )
break_list = []
for i in range(M):
    break_list.append( int( input() ) )

break_list.append(-10)
t = 0
fib = [0] * (N + 1)
if break_list[0] == 1:
    fib[1] = 0
    t += 1
else:
    fib[1] = 1
    
fib[0] = 1

for i in range(N - 1):
    if ( i + 2 ) ==  break_list[t]:
        fib[i + 2] = 0
        t += 1
    else:
        fib[i + 2] = fib[i] + fib[i + 1]
 
if N == 1:
    print( fib[1] )
else:
    print( fib[i+2] %  1000000007 )
def BubbleSort(A,n):
    count = 0
    for i in range(n):
        for j in range(n-1,i,-1):
            if A[j] < A[j-1]:
                A[j], A[j-1] = A[j-1], A[j]
                print (A[j], A[j-1])
                count += 1
    return A, count


n = int(input())
A = [int(input().rstrip(" ")) for i in range(n)]
count = 0
ans = 0
ans, count =  (BubbleSort(A,n))
ans = list(map(str,ans))

print (" ".join(ans))
print (count)

### FIXED CODE ###

n = int(input())
 
numbers = list(map(int, input().split(" ")))
 
cnt = 0
 
for i in range(n):
    for j in range(n - 1, i, -1):
        if numbers[j] < numbers[j - 1]:
            numbers[j],numbers[j - 1] = numbers[j - 1], numbers[j]
            cnt += 1
 
numbers = map(str, numbers)
print(" ".join(numbers))
 
print(cnt)
import math

N,X=map(int,input().split())
x=[int(i) for i in input().split()]
x.append(X)
x.sort()
d=[]
for i in range(N):
    d.append(x[i+1]-x[i])
n=d[0]
for i in range(N-1):
    n=math.gcd(n,d[i+1])
print(n)

### FIXED CODE ###

N,X=map(int,input().split())
x=list(map(int,input().split()))
x.append(X) #len(x)=N+1
x.sort()

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

init=x[0]
x=[i-init for i in x]
d=x[1]
for i in range(N-1):   # 0 2 4 6 10 14   N=5
    if d==0:
        d=x[i+2]
    else:
        d=gcd(d,x[i+2])
print(d)
A=list(input())
B=list(input())
A=list(input())
X=A
while True:
    if X[0] == "a":
        X = A
        X.pop(0)
        if len(X) == 0:
            print("A")
            break
    elif X[0] == "b":
        X = B
        X.pop(0)
        if len(X) == 0:
            print("B")
            break
    else:
        X = C
        X.pop(0)
        if len(X) == 0:
            print("C")
            break

### FIXED CODE ###

A = list(str(input()))
B = list(str(input()))
C = list(str(input()))
X="a"
while True:
    if X == "a":
        if len(A) == 0:
            print("A")
            break
        X = A[0]
        A.pop(0)
    elif X == "b":
        if len(B) == 0:
            print("B")
            break
        X = B[0]
        B.pop(0)
    else:
        if len(C) == 0:
            print("C")
            break
        X = C[0]
        C.pop(0)
def gen_pattern(N, pre=b""):
  for c in range(0x61, max(pre or 0x60)+2):
    pat = pre+c
    if len(pat) == N:
      yield pat.decode()
    else:
      yield from gen_pattern(N, pat)

for pattern in gen_pattern(int(input())):
  print(pattern)


### FIXED CODE ###

from itertools import product, combinations_with_replacement
N=int(input())
s="abcdefghij"
 
def get_gen(a, N):
  for c in s[:s.index(max(a))+2 if a else 1]:
    t = a+c
    if len(t) == N:
      print(t)
    else:
      get_gen(t,N)

get_gen("", N)
A,B=map(int,input().split())
lst=[]
i=2
while A>1 and B>1
    if A%i==0 and B%i==0:
        flag=1
        for l in lst:
            if i%l==0:
                flag=0
                break
        if flag:
            A=A//i
            B=B//i
            lst.append(i)
    i+=1

lst+=[1]
#print(lst)
print(len(lst))


### FIXED CODE ###

A,B=map(int,input().split())
lst=set()
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

if A==B==1:
    print(1)
else:
    print(len(set([i[0] for i in factorization(A)])&set([i[0] for i in factorization(B)]))+1)
def prison():
    N, M = (int(i) for i in input().split())
    L_max = 0
    R_min = float("inf")
    for _ in range(M):
        L, R = (int(i) for i in input().split())
        L_max = max(L, L_max)
        R_min = min(R, R_min)
	result = max(R_min - L_max + 1, 0)
    return result


print(prison())

### FIXED CODE ###

def prison():
    N, M = (int(i) for i in input().split())
    L_max = 0
    R_min = float("inf")
    for _ in range(M):
        L, R = (int(i) for i in input().split())
        L_max = max(L, L_max)
        R_min = min(R, R_min)
        result = max(R_min - L_max + 1, 0)
    return result


print(prison())
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

N, K = map(int, input().split())
X = list(map(int, input().split()))

ps = [0] + list(filter(lambda x: x >= 0, X))
ns = [0] + list(sorted(filter(lambda x: x < 0, X), reverse=True))
ans = INF
for i in range(len(ns)):
    val = abs(ns[i]) * 2
    if K - i < len(ps):
        val += abs(ps[K - i])
        ans = min(ans, val)
for i in range(len(ps)):
    val = abs(ps[i]) * 2
    if K - i < len(ns):
        val += abs(ns[K - i])
        ans = min(ans, val)
print(ans)


### FIXED CODE ###

import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 18
MOD = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

N, K = map(int, input().split())
X = list(map(int, input().split()))

ps = [0] + list(filter(lambda x: x >= 0, X))
ns = [0] + list(sorted(filter(lambda x: x < 0, X), reverse=True))

ans = INF
for i in range(len(ns)):
    val = abs(ns[i]) * 2
    if K - i >= 0 and K - i < len(ps):
        val += abs(ps[K - i])
        ans = min(ans, val)

for i in range(len(ps)):
    val = abs(ps[i]) * 2
    if K - i >= 0 and K - i < len(ns):
        val += abs(ns[K - i])
        ans = min(ans, val)
print(ans)
N=int(input())
A=list(map(int,input().split()))
A2=0
for i in ragne(len(A)):
  A2+=A[i]**2
c=(sum(A))**2-A2
print(c//2)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
c=0
d=sum(A)
for i in range(0,N-1):
    d-=A[i]
    c+=A[i]*d
    if(c>10**9+7):
        c%=(10**9+7)
print(c)
N = int(input())
A = list(map(int, input().split()))
Q = int(input())

table = [0] * 100001

c = 0
s = 0

for i in A:
    table[i] += 1
    s += i

print(su,s)

for i in range(Q):
    B, C = map(int,input().split())
    c = table[B]
    s += (C - B) * c
    table[C] += table[B]
    table[B] = 0
    print(s)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
S = []
c = 0
s = sum(A)
table = [0] * 100001
 
for i in A:
    table[i] += 1
 
for i in range(Q):
    B, C = map(int,input().split())
    c = table[B]
    s += (C - B) * c
    table[C] += table[B]
    table[B] = 0
    S.append(s)

for s in S:
    print(s)
X = int(input())
five = [0] * 70
five_inv = [0] * 70
for i in range(70):
  five[i] = i ** 5
  five_inv[i] = -five[i]

def check(x):
  for i in range(70):
    if X + five[i] in five:
      B = i
      A = five.index(five[i] + X)
      break
    elif X - five[i] in five:
      B = -i
      A = five.index(-five[i] + X)
      break
    elif X + five[i] in five_inv:
      B = i
      A = -five_inv.index(five[i] + X)
      break
    elif X - five[i] in five_inv:
      B = -i
      A = -five_inv.index(-five[i] + X)
      break
  return "{} {}".format(A,B)

print(check(X))

### FIXED CODE ###

X = int(input())
five = [0] * 200
five_inv = [0] * 200
for i in range(200):
  five[i] = i ** 5
  five_inv[i] = -five[i]

def check(x):
  A = 0
  B = 0
  for i in range(200):
    if X + five[i] in five:
      B = i
      A = five.index(five[i] + X)
      break
    elif X - five[i] in five:
      B = -i
      A = five.index(-five[i] + X)
      break
    elif X - five[i] in five_inv:
      B = -i
      A = -five_inv.index(-five[i] + X)
      break
  return "{} {}".format(A,B)

print(check(X))
import math
target = input()
def is_prime(n):
    for i in range(2, int(math.sqrt(n)) + 1):
        if n%i ==0:
            return False
    return True

not_found_flg = True
if target %2 == 0:
    target = target+1
result = 0
while not_found_flg:
    if (is_prime(target)):
        result = target
        break
    target = target+2

print(result)

### FIXED CODE ###

import math
def is_prime(n):
    for i in range(2, int(math.sqrt(n)) + 1):
        if n%i ==0:
            return False
    return True
 
target = int(input())
 
not_found_flg = True
if target == 2:
    print("2")
else:
    if target %2 == 0:
        target = target+1
    result = 0

    while not_found_flg:
        if (is_prime(target)):
            result = target
            break
        target = target+2
 
    print(result)
N = input()
h = map(int,input().split())
h = list(h)

dp = [99999999 for i in range(100)]
dp[0]=0

for i in range(int(N)):
    for j in range(i+1,i+2+1):
        if j<int(N) :
            dp[j]=min(dp[j],dp[i]+abs(h[i]-h[j]))

print(dp[int(N)-1])

### FIXED CODE ###

import sys
n =int(input())
h = map(int,input().split())
h = list(h)

dp = [sys.maxsize]*n
dp[0]=0

for i in range(n):
    for j in range(i+1,i+2+1):
        if j<n :
            dp[j]=min(dp[j],dp[i]+abs(h[i]-h[j]))

print(dp[n-1])
from functools import lru_cache

N = int(input())
ABC = [list(map(int, input().split(" "))) for _ in range(N)]

# l = [[0 for _ in range(3)] for _ in range(N+10)]
@lru_cache(maxsize=None)
def dp(i, use):
    if i == -1:
        return 0
    max_num = 0
    for k in range(3):
        if k == use:
            continue
        max_num = max(max_num, dp(i-1, k)+ABC[i][use])
    return max_num

print(max(dp(N-1, m) for m in range(3)))


### FIXED CODE ###

from functools import lru_cache
import sys

sys.setrecursionlimit(10**8)

N = int(input())
ABC = [list(map(int, input().split(" "))) for _ in range(N)]

l = [[None for _ in range(3)] for _ in range(N+10)]
# @lru_cache(maxsize=None)
def dp(i, use):
    if i == -1:
        return 0
    if l[i][use] != None:
        return l[i][use]
    max_num = 0
    for k in range(3):
        if k == use:
            continue
        max_num = max(max_num, dp(i-1, k)+ABC[i][use])
    l[i][use] = max_num 
    return max_num

print(max(dp(N-1, m) for m in range(3)))
N = int(input())

for i in range(N**0.5, 0, -1):
    div, mod = divmod(N)
    if not mod:
        print(len(str(min(div, N//div))))


### FIXED CODE ###

N = int(input())

for i in range(int(N**0.5)+1, 0, -1):
    div, mod = divmod(N, i)
    if not mod:
        print(len(str(max(div, N//div))))
        exit()
N,X=map(int,input().split())
L=list(map(int,input().split()))

ans,i,D=0,1,0

while D<=X:
    D+=L[i-1]
    ans+=1
    i+=1
    
print(ans)

### FIXED CODE ###

N,X=map(int,input().split())
L=list(map(int,input().split()))

ans,D=1,0

for l in L:
   D+=l
   if D<=X:
       ans+=1
       
print(ans)
N = int(input())

n_sq = N ** 0.5

n_sq_int = int(n_sq // 1)

#print(n_sq_int)

for i in reversed(range(n_sq_int)):
    if N % i == 0:
        ans = N // i
        print(ans + i - 2)
        exit()

### FIXED CODE ###

N = int(input())

n_hoge = int(N ** 0.5)
print

true_ans = 10 ** 12
for i in range(1,n_hoge+1):
    if N % i == 0:
        ans = N // i
        true_ans = min(ans + i - 2, true_ans)

print(true_ans)
n = int(input())
numbers = input()

lst = []
lst2 = []
lst3 = []
for i in range(n):
  pin = ''
  if numbers[i] not in lst:
    pin += numbers[i]
    lst.append(pin)
    for j in range(i+1, n):
      pin += numbers[j]
      if pin not in lst2:
        lst2.append(pin)
        for k in range(j+1, n):
          pin += numbers[k]
          if pin not in lst3:
            lst3.append(pin)
          pin = pin[0] + pin[1]
      pin = pin[0]
    if ('0' in lst) and ('1' in lst) and ('2' in lst) and ('3' in lst) and ('4' in lst) and ('5' in lst) and ('6' in lst) and ('7' in lst) and ('8' in lst) and ('9' in lst):
      break
print(lst2[:][1])
print(len(lst3))


### FIXED CODE ###

n = int(input())
numbers = input()

lst = []
ans = []
for i in range(n):
  pin = ''
  if numbers[i] not in lst:
    pin += numbers[i]
    lst.append(pin)
    lst2 = []
    for j in range(i+1, n):
      pin += numbers[j]
      if pin[1] not in lst2:
        lst2.append(pin[1])
        lst3 = []
        for k in range(j+1, n):
          pin += numbers[k]
          if pin[2] not in lst3:
            lst3.append(pin[2])
            ans.append(pin)
          if ('0' in lst3) and ('1' in lst3) and ('2' in lst3) and ('3' in lst3) and ('4' in lst3) and ('5' in lst3) and ('6' in lst3) and ('7' in lst3) and ('8' in lst3) and ('9' in lst3):
            break
          pin = pin[0] + pin[1]
      if ('0' in lst2) and ('1' in lst2) and ('2' in lst2) and ('3' in lst2) and ('4' in lst2) and ('5' in lst2) and ('6' in lst2) and ('7' in lst2) and ('8' in lst2) and ('9' in lst2):
        break
      pin = pin[0]
    if ('0' in lst) and ('1' in lst) and ('2' in lst) and ('3' in lst) and ('4' in lst) and ('5' in lst) and ('6' in lst) and ('7' in lst) and ('8' in lst) and ('9' in lst):
      break
print(len(ans))
import math

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

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

lcm = lcm(n, m)

str1 = ""
for i in range(lcm):
	str1 += "-"

for i in range(n):
	index = i * lcm // n + 1
	str1 = str1[:index] + s[i] + str1[index+1:]

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

if flg == 0:
	print(lcm)

### FIXED CODE ###

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)

# str1 = ""
# for i in range(lcm):
# 	str1 += "-"

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)


# 	str1 = str1[:index] + s[i] + str1[index+1:]

# flg = 0
# for i in range(m):
# 	index = i * lcm // m + 1
# 	if str1[index:index+1] != "-" and str1[index:index+1] != t[i]:
# 		print("-1")
# 		flg = 1
# 		break

# if flg == 0:
# 	print(lcm)
import math
H = int(input())
A = math.floor(math.log2(H))
print(2**(A+1)-1)

### FIXED CODE ###

import math
H = int(input())
A = math.floor(math.log2(H))
print(2**(A+1)-1)
def sieve(n): # エラトステネスの篩
    num = [1]*n
    num[0]=num[1]= 0
    for i in range(int(n**0.5)+1):
        if num[i]:
            for j in range(i**2,n,i):
                num[j] = 0
    return num # list ### 1なら素数0なら合成数

primes = sieve(10**5)
like_2017 = [0]
for i in range(1,len(primes)):
    if i <= 2:
        like_2017.append(like_2017[i-1])
    elif primes[i] == 1 and primes[(i+1)//2] == 1:
        like_2017.append(like_2017[i-1]+1)
    else:
        like_2017.append(like_2017[i-1])
Q = int(input())
for q in range(Q):
    l,r = map(int,input().split())
    print(like_2017[r+1]-like_2017[l-1])


### FIXED CODE ###

def sieve(n): # エラトステネスの篩
    num = [1]*n
    num[0]=num[1]= 0
    for i in range(int(n**0.5)+1):
        if num[i]:
            for j in range(i**2,n,i):
                num[j] = 0
    return num # list ### 1なら素数0なら合成数

primes = sieve(10**5)
like_2017 = [0]
for i in range(1,len(primes)):
    if i <= 2:
        like_2017.append(like_2017[i-1])
    elif primes[i] == 1 and primes[(i+1)//2] == 1:
        like_2017.append(like_2017[i-1]+1)
    else:
        like_2017.append(like_2017[i-1])
Q = int(input())
for q in range(Q):
    l,r = map(int,input().split())
    print(like_2017[r]-like_2017[l-1])