Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

n = int(input())

D = [[[-1]*(n+1) for _ in range(n+1)] for i in range(n+1)]
def dfs(b, c, d):
  if b == c == d == 0:
    return 0
  if D[b][c][d] != -1:
    return D[b][c][d]
  rep = n
  if b != 0:
    rep += b * dfs(b-1, c, d)
  if c != 0:
    rep += c * dfs(b+1, c-1, d)
  if d != 0:
    rep += d * dfs(b, c+1, d-1)
  rep /= (b+c+d)
  D[b][c][d] = rep
  return rep

L = [0]*3
for a in map(int, input().split()):
  L[a-1] += 1
ans = dfs(*L)
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
n = int(input())
A = tuple(map(int, input().split()))
C = [0]*3
for a in A:
  C[a-1] += 1
dp = [[[-1]*(n+1) for i in range(n+1)] for j in range(n+1)]
dp[0][0][0] = 0
def f(i, j, k):
  if dp[i][j][k] != -1:
    return dp[i][j][k]
  res = 1
  if i:
    res += f(i-1, j, k)*(i/n)
  if j:
    res += f(i+1, j-1, k)*(j/n)
  if k:
    res += f(i, j+1, k-1)*(k/n)
  res /= (i+j+k)/n
  dp[i][j][k] = res
  return res
ans = f(C[0], C[1], C[2])
print(ans)
### BUGGY CODE ###

def uauau():
    N = int(input())
    aA=sorted(set(int(_) for _ in input().split()))
    N = len(aA)
    def ggg(i,j):
        i %= j
        if i == 0:
            return j
        else:
            return ggg(j,i)

    if len(aA) == 1:
        print(aA[0])
    else:
        iMin = aA[0]
        iMax = aA[-1]
        if iMin  == 1:
            print(1)
        else:
            iMt = max(i % iMin for i in aA)
            if iMt == 0:
                print(iMin)
                exit()
            elif iMt  == 1:
                print (1)
            else:
                iM = iMax
                for i in range(N):
                    iA = aA[i]
                    for j in range(i+1,N):
                        iMt = ggg(aA[j],iA)
                        if 0 < iMt and iMt < iM:
                            iM = iMt
                    if iM == 1:
                        print(1)
                        exit()
                print(iM)
uauau()


### FIXED CODE ###

#gcdか....
def fgcd(a,b):
    while b:
        a,b = b,a%b
    return a

N = int(input())
aA = sorted(set(int(_) for _ in input().split()))
b = aA[0]
for a in aA[1:]:
    b = fgcd(a,b)
print(b)
### BUGGY CODE ###

def main():
    N = int(input())
    a_list = list(map(int, input().split()))
    mod = 10 ** 9 + 7

    sum = 0

    for i in range(60):
        count_1 = 0
        for a in a_list:
            bin_a = format(a, "b").zfill(60)
            if bin_a[59-i] == "1":
                count_1 += 1

        sum += 2 ** i * count_1 * (N - count_1)

    print(sum % mod)


if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    N = int(input())
    a_list = list(map(int, input().split()))
    mod = 10 ** 9 + 7

    t = [0]*60

    for a in a_list:
        for count, i in enumerate(reversed(format(a, "b"))):
            if i == "1":
                t[count] += 1

    sum = 0
    for i, count in enumerate(t):
        sum += 2 ** i * count * (N - count)
    print(sum % mod)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

MOD = 998244353
n, k = map(int, input().split())
s = set()
for i in range(k):
    a, b = map(int, input().split())
    s.update(range(a, b + 1))

dp = [0] + [-1] * n
def dfs(goal, route):
    if dp[goal] != -1:
        return dp[goal]
    else:
        ans = 0
        for r in route:
            if goal - r < 1:
                continue
            else:
                ans = (ans + dfs(goal - r, route)) % MOD
        dp[goal] = ans
        return dp[goal]
dp[1] = 1
print(dfs(n, s))


### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

MOD = 998244353
n, k = map(int, input().split())
s = list()
for i in range(k):
    s.append(tuple(map(int, input().split())))

dp = [0] + [0] * n
diff = [0] + [0] * n
dp[1] = 1
for i in range(1, n):
    for j, k in s:
        if i + j > n:
            continue
        diff[i + j] += dp[i]
        if i + k + 1 > n:
            continue
        diff[i + k + 1] -= dp[i]
    dp[i] = (dp[i - 1] + diff[i]) % MOD
    dp[i + 1] = (dp[i] + diff[i + 1]) % MOD
print(dp[n])
### BUGGY CODE ###

N = int(input())

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

res = 0
for i in range(1,N+1):
    res += i*make_divisors(i)
print(res)

### FIXED CODE ###

N = int(input())

res = 0
for i in range(1,N+1):
    n = N // i
    res += i * n * (n+1) // 2

print(res)
### BUGGY CODE ###

n = int(input())
S = [s for s in input()]
ans = float('inf')
for i in range(n):
    #print(S[:i],S[i+1:])
    ans = min(ans,S[:i].count('W')+S[i+1:].count('E'))
print(ans)


### FIXED CODE ###

n = int(input())
S = [s for s in input()]
e,w = [0],[0]
for i in range(n):
    if S[i] is 'W': e.append(e[i]+1)
    else:   e.append(e[i])
    if S[n-i-1] is 'E': w.append(w[i]+1)
    else:   w.append(w[i])
w = w[::-1]
ans = float('inf')
for i in range(n+1):
    ans = min(ans,e[i]+w[i])
print(ans)
### BUGGY CODE ###

from collections import defaultdict
from heapq import heappop, heappush
import sys
input = sys.stdin.buffer.readline
N,M,S = map(int,input().split())
UVAB = [list(map(int,input().split())) for i in range(M)]
U,V,A,B = zip(*UVAB)
mc = max(A)* M
g = defaultdict(list)

for u,v,a,b in UVAB:
    for i in range(a,mc+1):
        g[(u,i)].append(((v,i-a),b))
        g[(v,i)].append(((u,i-a),b))
CD = [[0,0]] + [list(map(int,input().split())) for i in range(N)]
C,D = zip(*CD)

for i in range(1,N+1):
    for c in range(mc+1-C[i]):
        g[(i,c)].append(((i,c+C[i]),D[i]))

S = min(S,mc)
dq = [((1,S),0)]

ans = [[10**15 for j in range(mc+1)] for i in range(N+1)]
while dq:
    (v, w), t = heappop(dq)
    if ans[v][w] < t:
        continue
    ans[v][w] = t
    for (nv,nw), nt in g[(v,w)]:
        if ans[nv][nw] > ans[v][w] + nt:
            ans[nv][nw] = ans[v][w] + nt 
            heappush(dq,((nv,nw),t+nt))

for i in range(2,N+1):
    print(min(ans[i]))






### FIXED CODE ###

from collections import defaultdict
from heapq import heappop, heappush,heapify
import sys
input = sys.stdin.readline

N,M,S = map(int,input().split())
UVAB = [list(map(int,input().split())) for i in range(M)]
U,V,A,B = zip(*UVAB)

'''
from itertools import combinations 
N = 14
M = N*(N-1)//2
S = 0
UVAB = [[x,y,50,10**9] for x,y in combinations(range(1,N+1),2)] 
U,V,A,B = zip(*UVAB)
'''

mc = max(A)* M
g = defaultdict(list)

for u,v,a,b in UVAB:
    for i in range(a,mc+1):
        g[(u,i)].append(((v,i-a),b))
        g[(v,i)].append(((u,i-a),b))

CD = [[0,0]] + [list(map(int,input().split())) for i in range(N)]
#CD = [[0,0]] + [[10**9,10**9] for i in range(N)]
C,D = zip(*CD)
C = [min(c,mc) for c in C]

for i in range(1,N+1):
    for c in range(mc+1-C[i]):
        g[(i,c)].append(((i,c+C[i]),D[i]))

S = min(S,mc)
dq = [(0,S,1)]

ans = [[10**15 for j in range(mc+1)] for i in range(N+1)]
while dq:
    t, w, v = heappop(dq)
    if ans[v][w] <= t:
        continue
    for i in range(w+1):
        ans[v][i] = min(t, ans[v][i])
    for (nv,nw), nt in g[(v,w)]:
        if ans[nv][nw] > t + nt:
            heappush(dq,(t+nt,nw,nv))

for i in range(2,N+1):
    print(min(ans[i]))
### BUGGY CODE ###

N, Q = map(int,input().split())
graph = {i:[] for i in range(N)}
G = {i:[] for i in range(N)}
ans = [0 for i in range(N)]
for i in range(N-1):
  a, b = map(int, input().split())
  graph[a-1] += [b-1]
  graph[b-1] += [a-1]
stuck = [0]
log = [0 for i in range(N)]
log[0]=1
ls = [0]
while stuck:
  x = stuck.pop()
  A = graph[x]
  flag = True
  ki = []
  for a in A:
    if log[a]==0:
      stuck += [a]
      ki+=[a]
      log[a]=1
      flag = False
  for l in ls:
    G[l] += ki
  ls += ki
  if flag:
    ls.remove(x)
for i in range(Q):
  p, x = map(int,input().split())
  p = p-1
  for l in G[p]:
    ans[l] += x
  ans[p] += x
A = map(str, ans)
print(' '.join(A))


### FIXED CODE ###

from collections import deque
N, Q = map(int, input().split())
G = [[] for _ in range(N)]
count = [0]*N
for i in range(N-1):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
for i in range(Q):
    p, x = map(int, input().split())
    count[p-1]+=x
q = deque([0])
flag = [False]*N
while q:
    v = q.pop()
    flag[v] = True
    for e in G[v]:
        if flag[e]:
            continue
        count[e]+=count[v]
        q.append(e)
print(*count)
### BUGGY CODE ###

import numpy as np
N,K = map(int,input().split())
people = np.array(sorted(list(map(int,input().split()))))
food = np.array(sorted(list(map(int,input().split())))[::-1])


#2分探索　Kの値で
_max = 10**12
_min = 0

while _max!=_min:
  mean = (_max+_min)//2
  # 各人が修行をする回数の配列　負の値もでる
  K_arr = np.maximum(0,people - mean//food)
  # 総修行回数
  _K = sum(K_arr)
  if _K > K:
    _min = mean+1
  else:
    _max = mean
    
print(_max)
  

### FIXED CODE ###

import sys
import numpy as np
readline = sys.stdin.buffer.readline

N,K = map(int,readline().split())
people = np.array(readline().split(),np.int64)
food = np.array(readline().split(),np.int64)
 
people.sort()
food.sort()
food=food[::-1]

#2分探索　Kの値で
_max = max(people)*max(food)
_min = 0

while _max>_min:
  mean = (_max+_min)//2
  # 各人が修行をする回数の配列　負の値もでる
  _K = np.maximum(0,people - mean//food).sum()
  if _K > K:
    _min = mean+1
  else:
    _max = mean
    
print(_max)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def main():
    n=int(input()[:-1])
    a=[list(map(int, input().split()))[::-1] for _ in range(n)]
    all_g=n*(n-1)//2
    g=0
    d=0
    while 1:
        d+=1
        finish=set()
        for i in range(n):
            if i in finish:continue
            if a[i]==[]:continue
            ii=a[i][-1]-1
            if a[ii][-1]-1==i:
                g+=1
                finish.add(ii)
                finish.add(i)
        if g==all_g:
            print(d)
            break
        if not finish:
            print(-1)
            break
        for ii in finish:
            a[ii].pop()

main()

### FIXED CODE ###

# YouTube1

def main():
    n = int(input())
    a = [list(map(lambda x: int(x) - 1, input().split()))[::-1] for _ in range(n)]
    #    print(a)
    gam = []  # １日のgames
    # 初期化
    for i in range(n):
        ii = a[i][-1]
        if ii < i: continue
        if a[ii][-1] == i:
            gam.append([i, ii])
    days = 0
    fin = [False] * n
    fin_cnt = 0
    #    print(gam)
    while 1:
        days += 1
        pla = []  # 今日試合があったplayers
        for i, ii in gam:
            a[i].pop()
            a[ii].pop()
            pla.append(i)
            pla.append(ii)
        gam = []
        dec = set()
        for i in pla:
            if fin[i]: continue
            if not a[i]:
                fin[i] = True
                fin_cnt += 1
                if fin_cnt == n:
                    print(days)
                    exit()
                continue
            if i in dec: continue
            ii = a[i][-1]
            if a[ii][-1] == i:
                gam.append([i, ii])
                dec.add(ii)
        if not gam:
            print(-1)
            exit()

main()
### BUGGY CODE ###

#!/usr/bin/env python3
n, *d = map(int, open(0).read().split())
a = d[::2]
b = d[1::2]
s = 0
for i in range(n):
    t = a[-i-1] % b[-i-1]
    if t: t = b[-i-1] - t
    *a, = map(lambda x: x+t, a)
    s += t
print(s)

### FIXED CODE ###

#!/usr/bin/env python3
_, *s = open(0)
c = 0
for t in s[::-1]:
    a, b = map(int, t.split())
    c += (-a-c) % b
print(c)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
import re
def print_ans(S):
    """Test Case
    >>> print_ans("0011")
    4
    >>> print_ans("11011010001011")
    12
    >>> print_ans("0")
    0
    """
    flg = True
    ans = 0
    while flg:
        tmp = re.search(r"01|10", S)
        if tmp == None:
            flg = False
        else:
            S = S[:tmp.start()] + S[tmp.start() + 2:]
            ans += 2
    print(ans)
        


if __name__ == '__main__':
    S = input().rstrip()
    print_ans(S)


### FIXED CODE ###

import sys
input = sys.stdin.readline
import re
def print_ans(S):
    """Test Case
    >>> print_ans("0011")
    4
    >>> print_ans("11011010001011")
    12
    >>> print_ans("0")
    0
    """
    flg = True
    ans = 0
    # while flg:
    #     tmp = re.sub(r"01|10", "", S)
    #     if len(tmp) == len(S):
    #         flg = False
    #         break
    #     else:
    #         ans += len(S) - len(tmp)
    #         S = tmp
    # print(ans)
    list_0 = []
    list_1 = []
    for s in S:
        if s =="0":
            list_0.append(s)
        else:
            list_1.append(s)
    print(min(len(list_0), len(list_1)) * 2)
        


if __name__ == '__main__':
    S = input().rstrip()
    print_ans(S)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10**7)
# input = sys.stdin.readline

n, q = map(int, input().split())
graph = {i: [] for i in range(n)}
for a, b in [[int(i)-1 for i in input().split()] for _ in range(n-1)]:
    graph[a].append(b)
    graph[b].append(a)
ans = [0] * n
for p, x in [[int(i) for i in input().split()] for _ in range(q)]:
    ans[p-1] += x

def dfs(now, parent):
    if parent != -1:
        ans[now] += ans[parent]
    for i in graph[now]:
        if i == parent:
            continue
        dfs(i, now)

dfs(0, -1)
print(' '.join(map(str, ans)))


### FIXED CODE ###

import sys

sys.setrecursionlimit(10**7)
input = sys.stdin.readline

n, q = map(int, input().split())
graph = {i: [] for i in range(n)}
for a, b in [[int(i)-1 for i in input().split()] for _ in range(n-1)]:
    graph[a].append(b)
    graph[b].append(a)
ans = [0] * n
for p, x in [[int(i) for i in input().split()] for _ in range(q)]:
    ans[p-1] += x

def dfs(now, parent):
    if parent != -1:
        ans[now] += ans[parent]
    for i in graph[now]:
        if i == parent:
            continue
        dfs(i, now)

dfs(0, -1)
print(' '.join(map(str, ans)))
### BUGGY CODE ###

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

from collections import deque

an = list(map(int, input().split()))

bn = list(map(int, input().split()))

an = an
bn = bn

vMax = 10**9+10

import itertools

accum_a = [0]
accum_b = [0]

dp = [[0]*200003]*200003
candidate = []
for a_i in range(0,len(an)):


    sumCandidate = accum_a[-1] + an[a_i]
    if sumCandidate > k:
        break
    accum_a.append(sumCandidate)

for b_i in range(0,len(bn)):
    accum_b.append(accum_b[-1]+ bn[b_i])

countMax = 0
for i, aSum in enumerate(accum_a):
    rest = k - aSum

    bIndex = 0
    for j, accB in enumerate(accum_b):
        if accB > rest:
            bIndex = max(0, j-1)
            break
        bIndex = j

    countMax = max(countMax, i + bIndex)

print(countMax)

### FIXED CODE ###

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

from collections import deque

an = list(map(int, input().split()))

bn = list(map(int, input().split()))

accum_a = [0]
accum_b = [0]


for a_i in range(0,len(an)):

    sumCandidate = accum_a[-1] + an[a_i]
    if sumCandidate > k:
        break
    accum_a.append(sumCandidate)

for b_i in range(0,len(bn)):
    i_ = accum_b[-1] + bn[b_i]
    if i_ > k:
        break
    accum_b.append(i_)

j = len(accum_b) - 1
ans = 0
for i in range(len(accum_a)):

    if accum_a[i] > k:
        break

    while accum_b[j] > k - accum_a[i]:
        j -= 1

    ans = max(ans, i+j)
print(ans)
### BUGGY CODE ###

n=int(input())
d={}
for k in range(2, 10**6):
  while n%k<1: n//k; d[k]=d.get(k, 0)+1
a=0
for i in d.values():
  t=c=0
  while t+c<i: c+=1; t+=c
  a+=c
print(a+(n>1))


### FIXED CODE ###

n=int(input())
d={}
for k in range(2,10**6):
  while n%k<1: n//=k; d[k]=d.get(k,0)+1
a=0
for i in d.values():
  t=c=0
  while t+c<i: c+=1; t+=c
  a+=c
print(a+(n>1))
### BUGGY CODE ###

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

all_sum = 0
count = 1

for i in range(n - 1):
  all_sum += a[i] * sum(a[count:len(a)])
  count += 1

print(all_sum % (10 ** 9 + 7))

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
s = sum(a)

all_sum = 0
count = 1

for i in range(n - 1):
  s -= a[i]
  all_sum += a[i] * s

print(all_sum % (10 ** 9 + 7))
### BUGGY CODE ###

n, m = map(int, input().split())
s = input()
dp = [-1 for _i in range(n+1)]
dp[0] = 0
for i in range(1, n+1):
    if i <= m:
        if s[i]=="0":
            dp[i] = 0
        continue
    for j in range(max(0,i-m), i):
        if s[j]=="0" and dp[j] >= 0:
            dp[i] = j
            break


if dp[n] >= 0:
    r = []
    p = n
    while p > 0:
        nex = dp[p]
        r.append(p-nex)
        p = nex
    print(*r[::-1])
else:
    print(-1)

### FIXED CODE ###

n, m = map(int, input().split())
s = input()
dp = [-1 for _i in range(n+1)]
dp[0] = 0
f = 0
from collections import deque
q = deque([0])
c = 0
for i in range(1, n+1):
    if s[i]=="0":
        c = 0
        while i-f > m:
            f = q.popleft()
        dp[i] = f
        q.append(i)
    else:
        c += 1
        if c >= m:
            break

if dp[n] >= 0:
    r = []
    p = n
    while p > 0:
        nex = dp[p]
        r.append(p-nex)
        p = nex
    print(*r[::-1])
else:
    print(-1)
### BUGGY CODE ###

x = [0] * 3
x[0], x[1], x[2], N = map(int, input().split())
A = [[0]*(N+1) for _ in range(4)]
A[0][0] = 1

for k in range(3):
    for i in range(N+1):
        j = 0
        while i + x[k] * j <= N:
            A[k+1][i + x[k] * j] += A[k][i]
            j += 1

print(A[3][N])

### FIXED CODE ###

x = [0] * 3
x[0], x[1], x[2], N = map(int, input().split())
A = [[0]*(N+1) for _ in range(4)]
A[0][0] = 1

for k in range(3):
    for i in range(N+1):
        j = 0
        while i + x[k] * j <= N:
            A[k+1][i + x[k] * j] += A[k][i]
            j += 1

print(A[3][N])
### BUGGY CODE ###

n = input()
a = [i for i in n]
ans = 0
n = len(n)
for j in range(20000):
    flag = 1
    for i in range(n-2,-1,-1):
        if a[i+1] == "W" and a[i] == "B":
            a[i] = "W"
            a[i+1] = "B"
            ans += 1
            flag = 0
            x = i+1
            while x<n-1:
                if a[x+1] == "W" and a[x] == "B":
                    a[x] = "W"
                    a[x+1] = "B"
                    ans += 1
                    x+=1
                else:
                    break
    if flag ==1:
        break
print(ans)

### FIXED CODE ###

n = input()
a = [i for i in n]
ans = 0
n = len(n)
B=0
W = 0
for i in range(n):
    if a[i] == "W":
        ans += i-W
        W+=1
print(ans)
### BUGGY CODE ###

import sys
from heapq import heappush as hpu
from heapq import heappop as hpo
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

base = 10 ** 10
sb = [(-b[i], i) for i in range(N) if a[i] != b[i]]
h = []
for t in sb: hpu(h, t)
res = 0
while len(h):
  v, i = hpo(h)
  v = -v
  if v < a[i]:
    print(-1)
    exit(0)
  d = v - a[i]
  x = b[i - 1] + b[(i + 1) % N]
  t = d // x
  if t == 0:
    if v == a[i]: continue
    print(-1)
    exit(0)
  b[i] -= x * (t)
  res += t
  hpu(h, (-b[i], i))
print(res)


### FIXED CODE ###

import sys
from heapq import heappush as hpu
from heapq import heappop as hpo
input = sys.stdin.readline
N = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

base = 10 ** 6
sb = [-(b[i] * base + i) for i in range(N) if a[i] != b[i]]
h = []
for t in sb: hpu(h, t)
res = 0
while len(h):
  v = hpo(h)
  i = -v % base
  v = -v // base
  if v < a[i]:
    print(-1)
    exit(0)
  d = v - a[i]
  x = b[i - 1] + b[(i + 1) % N]
  t = d // x
  if t == 0:
    if v == a[i]: continue
    print(-1)
    exit(0)
  b[i] -= x * (t)
  res += t
  hpu(h, -(b[i] * base + i))
print(res)
### BUGGY CODE ###

n = int(input())
table = [[] for _ in range(n+1)]
for i in range(1, n+1):
  a = list(map(int, input().split()))
  table[i] = a
cursor = [0]*(n+1)
is_matched = set()
d = 0
match = 0
while match < n * (n-1) //2:
  now_match = match
  for i in range(1, n):
    if cursor[i] < n-1 and i not in is_matched:
      j = table[i][cursor[i]]
      if i < j and j not in is_matched and table[j][cursor[j]] == i :
        match += 1
        cursor[i] += 1
        is_matched.add(i)
        cursor[j] += 1
        is_matched.add(j)
  if now_match == match:
    print(-1)
    exit()
  if d > 50000:
    print(499500)
    exit()  
  d += 1
  is_matched.clear()
print(d)

### FIXED CODE ###

n = int(input())
table = [[] for _ in range(n+1)]
for i in range(1, n+1):
  a = list(map(int, input().split()))
  table[i] = a
cursor = [0]*(n+1)
is_matched = set()
d = 0
match = 0
while match < n * (n-1) //2:
  now_match = match
  for i in range(1, n):
    if cursor[i] < n-1 and i not in is_matched:
      j = table[i][cursor[i]]
      if i < j and j not in is_matched and table[j][cursor[j]] == i :
        match += 1
        cursor[i] += 1
        is_matched.add(i)
        cursor[j] += 1
        is_matched.add(j)
  if now_match == match:
    print(-1)
    exit()
  if d > 30000:
    print(499500)
    exit()  
  d += 1
  is_matched.clear()
print(d)
### BUGGY CODE ###

from fractions import gcd
N,M=(int(i) for i in input().split())
S=input()
T=input()
gcd_NM=gcd(N,M)
L=(N*M//gcd_NM)
LN=[1+(L//N)*i for i in range(N)]
LM=[1+(L//M)*i for i in range(M)]
L_NM=list(set(LN)&set(LM))
A=True
for i in L_NM:
  if S[LN.index(i)]!=T[LM.index(i)]:
    A=False
    break
if A is True:
  print(L)
else:
  print(-1)

### FIXED CODE ###

from fractions import gcd
N,M=(int(i) for i in input().split())
S=input()
T=input()
gcd_NM=gcd(N,M)
lcm_NM=(N*M//gcd_NM)
A=True
for i in range(gcd_NM):
  if S[(N//gcd_NM)*i]!=T[(M//gcd_NM)*i]:
    A=False 
    break
if A:
  print(lcm_NM)
else:
  print(-1)