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

import sys
from functools import lru_cache
sys.setrecursionlimit(10**9)


def solve(x1, x2, x3):
    if seen[x1][x2][x3]:
        return dp[x1][x2][x3]
    if x1 == x2 == x3 == 0:
        return 0
    eat1 = solve(x1-1, x2, x3)*(x1/N) if x1 > 0 else 0
    eat2 = solve(x1+1, x2-1, x3)*(x2/N) if x2 > 0 else 0
    eat3 = solve(x1, x2+1, x3-1)*(x3/N) if x3 > 0 else 0
    dp[x1][x2][x3] = (1 + eat1 + eat2 + eat3) * (N/(x1+x2+x3))
    seen[x1][x2][x3] = 1
    return (1 + eat1 + eat2 + eat3) * (N/(x1+x2+x3))


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

cnt = [0] * 4
for i in range(N):
    cnt[a[i]] += 1

seen = [[[0 for _ in range(cnt[3]+1)] for _ in range(cnt[3] + cnt[2]+1)] for _ in range(cnt[3] + cnt[2] + cnt[1]+1)]
dp = [[[0 for _ in range(cnt[3]+1)] for _ in range(cnt[3] + cnt[2]+1)] for _ in range(cnt[3] + cnt[2] + cnt[1]+1)]
print(solve(cnt[1], cnt[2], cnt[3]))


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline

    N = int(input())
    A = list(map(int, input().split()))

    cnt = [0] * 3
    for a in A:
        cnt[a-1] += 1

    dp = [[[0.] * (N+1) for _ in range(N+1)] for _ in range(N+1)]
    for k in range(N+1):
        for j in range(N+1-k):
            for i in range(N+1-j-k):
                ijk = float(i + j + k)
                if ijk == 0:
                    continue
                x = N / ijk
                tmp = 0
                if i > 0:
                    tmp += (dp[i-1][j][k] + x) * (i / ijk)
                if j > 0 and i < N:
                    tmp += (dp[i+1][j-1][k] + x) * (j / ijk)
                if k > 0 and j < N:
                    tmp += (dp[i][j+1][k-1] + x) * (k / ijk)
                dp[i][j][k] = tmp
    print(dp[cnt[0]][cnt[1]][cnt[2]])


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

# B
N = int(input())
A_list = list(map(int, input().split()))

A_dict = dict()
for a in A_list:
    if a in A_dict.keys():
        A_dict[a] += 1
    else:
        A_dict[a] = 1

res = 0
A_list_ = list(reversed(sorted(A_list)))
for a in A_list_:
    # partner
    r = 1
    while r < a:
        r *= 2
    if a == r:
        res += A_dict[a] // 2
        A_dict[a] = 0
    else:
        b = r - a
        if A_dict[a] > 0 and A_dict.get(b, 0) > 0:
            A_dict[a] -= 1
            A_dict[b] -= 1
            res += 1
print(res)

### FIXED CODE ###

# B
import math

N = int(input())
A_list = list(map(int, input().split()))

A_dict = dict()
for a in A_list:
    if a in A_dict.keys():
        A_dict[a] += 1
    else:
        A_dict[a] = 1

res = 0
A_list_ = list(reversed(sorted(A_list)))
for a in A_list_:
    # partner
    r = 2**math.ceil(math.log2(a))
    if a == r:
        res += A_dict[a] // 2
        A_dict[a] = 0
    else:
        b = r - a
        if A_dict[a] > 0 and A_dict.get(b, 0) > 0:
            A_dict[a] -= 1
            A_dict[b] -= 1
            res += 1
print(res)
### BUGGY CODE ###

n = int(input())
s = []
for i in range(n):
  s.append(input())

t = list(set(s))

p = []
for j in t:
  p.append([s.count(j), j])

a = []
b = 0
q = 0
for k in sorted(p, reverse = True):
  if k[0] >= b:
    a.append(k[1])
    q +=1
    b = k[0]

for l in sorted(a):
  print(l)
  

### FIXED CODE ###

N = int(input())

d = {}
for _ in range(N):
  S = input()
  if S in d:
    d[S] += 1
  else:
    d[S] = 1

m = max(d.values())
for s in sorted(k for k in d if d[k] == m):
  print(s)
### BUGGY CODE ###

import numpy as np

#1. input
N = int(input())
A = list(map(int, input().split()))
A = np.array(A)

ans = [np.sum(np.abs(np.r_[A[:i], A[i+1:], 0] \
                                    - np.r_[0, A[:i], A[i+1:]])) for i in range(N)]
for i in range(N):
    print(ans[i])

### FIXED CODE ###

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

#2. make distance list
a.append(0)
a.insert(0,0)
costs = []

for i in range(n+1):
    costs.append(abs(a[i+1]-a[i]))

#3. calculate each cost
total = sum(costs)
for i in range(n):
    print(total - costs[i] - costs[i+1] + abs(a[i+2]-a[i]))
### BUGGY CODE ###

mod = 10**9+7

def cmb(n, r, mod):
    a, b = 1, 1
    for i in range(n, n - r, -1):
        a = a * i
    for i in range(r, 1, -1):
        b = b * i
    return a // b % mod
        


X, Y = map(int, input().split())

if not (X+Y) % 3 == 0:
    print(0)
else:
    n = (Y - 2*X) // -3
    m = X - (2 * n)
    if n < 0 or m < 0:
        print(0)
    else:
        print(cmb(n+m, n, mod))


### FIXED CODE ###

def cmb(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

mod = 10**9+7 #出力の制限
N = 10**6
g1 = [1, 1] # 元テーブル
g2 = [1, 1] #逆元テーブル
inverse = [0, 1] #逆元テーブル計算用テーブル

for i in range( 2, N + 1 ):
    g1.append( ( g1[-1] * i ) % mod )
    inverse.append( ( -inverse[mod % i] * (mod//i) ) % mod )
    g2.append( (g2[-1] * inverse[-1]) % mod )



X, Y = map(int, input().split())

if not (X+Y) % 3 == 0:
    print(0)
else:
    # 2n + m = X
    # n + 2m = Y
    n = (Y - 2*X) // -3
    m = X - (2 * n)
    if n < 0 or m < 0:
        print(0)
    else:
        print(cmb(n+m, n, mod))
### BUGGY CODE ###

n, c = map(int, input().split())
x = [0] * (n + 1)
v = [0] * (n + 1)
for i in range(1, n + 1):
    x[i], v[i] = map(int, input().split())

ans = 0

for i in range(n + 1):
    d = x[i]
    s = v[:i + 1]
    k = sum(s) - d
    if k > ans:
        ans = k

for j in range(n + 1):
    d = c - x[j]
    s = v[j:]
    k = sum(s) - d
    if k > ans:
        ans = k

for i in range(1, n + 1):
    d1r = 2 * x[i]
    d1l = x[i]
    s1 = sum(v[:i + 1])
    for j in range(i + 1, n + 1):
        d2r = c - x[j]
        s = s1 + sum(v[j:])
        k = s - (d1r + d2r)
        if k > ans:
            ans = k
        d2l = 2 * d2r
        k = s - (d1l + d2l)
        if k > ans:
            ans = k

print(ans)

### FIXED CODE ###

from itertools import accumulate

N, C = map(int, input().split())
sushi = [[int(x) for x in input().split()] for _ in range(N)]


def solve():
    """
    O(N)
    Bを固定したときの最適なAを事前に計算
    """
    V = [0] * (N + 1)
    for i in range(N):
        V[i + 1] = V[i] + sushi[i][1]

    f1 = [0] + [V[a + 1] - sushi[a][0] for a in range(N)]
    f2 = [0] + [V[a + 1] - 2 * sushi[a][0] for a in range(N)]

    g1 = [x for x in accumulate(f1, max)]
    g2 = [x for x in accumulate(f2, max)]

    ans = 0
    for j in range(N + 1):
        # OA
        if j == 0:
            i = N
        else:
            i = j - 1

        # OB
        if j == 0:
            ob_x = 0
        else:
            ob_x = C - sushi[j - 1][0]
        ob_v = V[N] - V[j - 1]

        # 2OA + OB
        ans = max(ans, g2[i] + ob_v - ob_x)

        # OA + 2OB
        ans = max(ans, g1[i] + ob_v - 2 * ob_x)
    print(ans)


solve()
### BUGGY CODE ###

N=int(input())
x=y=z=1

for i in range(1, N+1, 1):
    ans = [[x,y,z] for x in range(1,i+1,1) for y in range(1,i+1,1) for z in range(1,i+1,1) if x*x+y*y+z*z+x*y+y*z+z*x == i]
    print(len(ans))

### FIXED CODE ###

n = int(input())
 
ans = [0] * (n+1)
for x in range(1,110):
    for y in range(1,110):
        for z in range(1,110):
            tmp = x ** 2 + y ** 2 + z ** 2 + x * y + y * z + z * x
            if tmp <= n:
                ans[tmp] += 1
 
for i in ans[1:]:
    print(i)
### BUGGY CODE ###

 #ランレングス圧縮とは RLE(Run Length Encoding)とも言われます。
#連続したデータを、ひとつ分のデータと連続した長さで表現します。
def rle(s):
    tmp, count, ans = s[0], 1, []
    for i in range(1,len(s)):
        if tmp == s[i]:
            count += 1
        else:
            ans.append((tmp,count))
            tmp = s[i]
            count = 1
    ans.append((tmp,count))
    return ans

   # AAABBCCCCA ⇒ A3B2C4A1

# 初期入力
import sys
input = sys.stdin.readline
N,K = (int(x) for x in input().split())
S =input().strip()

#0と1が何回続くか
a =rle(S)
a_len =len(a)
count =[0]*a_len
ans =0

if K >= (a_len +1)//2:
    ans =N
else:
    for i in range(a_len):
        j =0
        count_0 =0
        while count_0 <K and i+j <a_len and j <a_len:
            count[i] +=a[i+j][1]
            if a[i+j][0]=="0":
                count_0 +=1
                if count_0 ==K and i+j+1 <a_len :
                    count[i] +=a[i+j+1][1]
            j +=1
    ans =max(count)
print(ans)

### FIXED CODE ###

 #ランレングス圧縮とは RLE(Run Length Encoding)とも言われます。
#連続したデータを、ひとつ分のデータと連続した長さで表現します。
def rle(s):
    tmp, count, ans_c,ans_n = int(s[0]),1,[] , []
    for i in range(1,len(s)):
        if tmp == int(s[i]):
            count += 1
        else:
            ans_c.append(tmp)
            ans_n.append(count)
            tmp = int(s[i])
            count = 1
    ans_c.append(tmp)
    ans_n.append(count)
    return ans_c,ans_n

# 初期入力
import sys
input = sys.stdin.readline
N,K = (int(x) for x in input().split())
S =input().strip()

#0と1が何回続くか
a_c,a_n =rle(S)
a_len =len(a_c)
a_n +=[0]
count =[0]*a_len
ans =0

#
if K >= (a_len +1)//2:
    ans =N
elif a_len==2:
    ans =N
elif a_len ==3 and a_c[0]==1:
    ans=N
else:
    if a_c[0] ==1:
        i=2
        indx =i +2*K 
        count[0] =sum(a_n[:0 +2*K +1])
        while not(indx ==a_len+2 or indx ==a_len+1):
            count[i] =count[i-2] -a_n[i-2] -a_n[i-1] + a_n[indx-1] +a_n[indx]
            i +=2
            indx =i +2*K 
    else:
        count[0] =sum(a_n[:2*K])
        count[1] =sum(a_n[1: 1+2*K+1])
        i=3
        indx =i +2*K 
        while not(indx ==a_len+2 or indx ==a_len+1):
            count[i] =count[i-2] -a_n[i-2] -a_n[i-1] + a_n[indx-1] +a_n[indx]
            i +=2      
            indx =i +2*K 
    ans =max(count)
print(ans)
### BUGGY CODE ###

n, m = map(int, input().split())
a = [0 for i in range(m)]
b = [0 for i in range(m)]
c = []
for i in range(m):
    a[i], b[i] = map(int, input().split())
    c.append(list(map(int, input().split())))

dp = [10**6 for i in range(2**n)]
dp[0] = 0

string = [0 for i in range(n)]
for i in c[0]:
    string[i-1] = 1
string = ''.join(map(str, string))
num = int(string, 2)
dp[num] = a[0]

for i in range(1, m):
    string = [0 for i in range(n)]
    for j in c[i]:
        string[j-1] = 1
    string = ''.join(map(str, string))
    di = int(string, 2)
    for j in range(2**n):
        dp[j|di] = min(dp[j|di], dp[j]+a[i])

if dp[2**n-1] != 10**6:
    print(dp[2**n-1])
else:
    print(-1)

### FIXED CODE ###

n, m = map(int, input().split())
a = [0 for i in range(m)]
b = [0 for i in range(m)]
c = []
for i in range(m):
    a[i], b[i] = map(int, input().split())
    c.append(list(map(int, input().split())))

dp = [10**6 for i in range(2**n)]
dp[0] = 0

string = [0 for i in range(n)]
for i in c[0]:
    string[i-1] = 1
string = ''.join(map(str, string))
num = int(string, 2)
dp[num] = a[0]

for i in range(1, m):
    string = [0 for i in range(n)]
    for j in c[i]:
        string[j-1] = 1
    string = ''.join(map(str, string))
    di = int(string, 2)
    for j in range(2**n):
        dp[j|di] = min(dp[j|di], dp[j]+a[i])

if dp[2**n-1] != 10**6:
    print(dp[2**n-1])
else:
    print(-1)
### BUGGY CODE ###

N=int(input())
S=input()
cnt=0
for i in range(N-2):
    for j in range(i+1,N-1):
        for k in range(j+1,N):
            if (S[i]!=S[j]) and (S[j]!=S[k]) and (S[k]!=S[i]) and ((k-j)!=(j-i)):
                cnt+=1
            else:
                continue
print(cnt)

### FIXED CODE ###

N=int(input())
S=input()
r=S.count('R')
b=S.count('B')
g=S.count('G')
ans=r*b*g
for i in range(N):
    for s in range(N):
        j=i+s
        k=j+s
        if k>=N:
            break
        if S[i]!=S[j] and S[j]!=S[k] and S[k]!=S[i]:
            ans-=1
print(ans)
### BUGGY CODE ###

n = int(input())
ga, sa, ba = list(map(int, input().split()))
gb, sb, bb = list(map(int, input().split()))

w_ab = []
v_ab = []

if ga < gb:
    w_ab.append(ga)
    v_ab.append(gb)
if sa < sb:
    w_ab.append(sa)
    v_ab.append(sb)
if ba < bb:
    w_ab.append(ba)
    v_ab.append(bb)

dp = [[0]*(n+1) for i in range(len(w_ab)+1)]
for i in range(len(w_ab)):
    for j in range(n+1):
        if j < w_ab[i]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j], dp[i+1][j - w_ab[i]] + v_ab[i])
ans = 0
for i in range(n+1):
    ans = max(ans, dp[len(w_ab)][i] + n-i)
n = ans

w_ab = []
v_ab = []

if ga > gb:
    w_ab.append(gb)
    v_ab.append(ga)
if sa > sb:
    w_ab.append(sb)
    v_ab.append(sa)
if ba > bb:
    w_ab.append(bb)
    v_ab.append(ba)

dp = [[0]*(n+1) for i in range(len(w_ab)+1)]
for i in range(len(w_ab)):
    for j in range(n+1):
        if j < w_ab[i]:
            dp[i+1][j] = dp[i][j]
        else:
            dp[i+1][j] = max(dp[i][j], dp[i+1][j - w_ab[i]] + v_ab[i])
ans = 0
for i in range(n+1):
    ans = max(ans, dp[len(w_ab)][i] + n-i)
print(ans)
  

### FIXED CODE ###

n = int(input())
ga, sa, ba = list(map(int, input().split()))
gb, sb, bb = list(map(int, input().split()))

w_ab = []
v_ab = []

if ga < gb:
    w_ab.append(ga)
    v_ab.append(gb)
if sa < sb:
    w_ab.append(sa)
    v_ab.append(sb)
if ba < bb:
    w_ab.append(ba)
    v_ab.append(bb)

num = (n+1)*(len(w_ab)+1)
dp = [0]*num
for i in range(len(w_ab)):
    for j in range(n+1):
        if j < w_ab[i]:
            dp[(i+1)*(n+1) + j] = dp[i*(n+1) + j]
        else:
            dp[(i+1)*(n+1) + j] = max(dp[i*(n+1) + j], dp[(i+1)*(n+1) + j - w_ab[i]] + v_ab[i])
ans = 0
length = len(w_ab)
for j in range(n+1):
    ans = max(ans, dp[length*(n+1) + j] + n-j)
n = ans

w_ab = []
v_ab = []

if ga > gb:
    w_ab.append(gb)
    v_ab.append(ga)
if sa > sb:
    w_ab.append(sb)
    v_ab.append(sa)
if ba > bb:
    w_ab.append(bb)
    v_ab.append(ba)

num = (n+1)*(len(w_ab)+1)
dp = [0]*num
for i in range(len(w_ab)):
    for j in range(n+1):
        if j < w_ab[i]:
            dp[(i+1)*(n+1) + j] = dp[i*(n+1) + j]
        else:
            dp[(i+1)*(n+1) + j] = max(dp[i*(n+1) + j], dp[(i+1)*(n+1) + j - w_ab[i]] + v_ab[i])

length = len(w_ab)
ans = 0
for j in range(n+1):
    ans = max(ans, dp[length*(n+1) + j] + n-j)
print(ans)
### BUGGY CODE ###

n, m = map(int, input().split())
count = 0
ans = []
pen = []
penal = 0
p = [0]*m
x = [0]*m
for i in range(m):
    p[i], x[i] = map(str, input().split())
    if x[i] == "AC":
        ans.append(p[i])
    elif x[i] == "WA":
        for j in range(len(ans)):
            if p[i] == ans[j]:
                penal -= 1
                break
        penal += 1
        pen.append((p[i], x[i]))
    if len(ans) == n:
        break


ans = list(set(ans))

for i in range(len(pen)):
    if pen[i][0] not in ans:
        penal -= 1

if penal < 0:
    penal = 0

print("{}".format(len(ans)) + " {}".format(penal))

### FIXED CODE ###

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

problem = [0] * n
count = [0] * n

penal = 0

for i in range(m):
    p, x = map(str, input().split())
    p = int(p) - 1
    if x == "AC":
        if problem[p] == 0:
            problem[p] = 1
    elif x == "WA":
        if problem[p] == 0:
            count[p] += 1

for i in range(n):
    if problem[i] == 0:
        count[i] = 0

print("{}".format(sum(problem)) + " {}".format(sum(count)))
### BUGGY CODE ###

def gcd(m, n):
    a, b = m, n
    r = a % b
    while r != 0:
        a, b = b, r
        r = a % b
    return b

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


a, b = map(int, input().split())

CD = divisors(gcd(a, b))

ans = 1
for cd in CD:
    if len(divisors(cd)) == 2:
        ans += 1

print(ans)


### FIXED CODE ###

def gcd(x, y):
    a, b = x, y
    r = a % b
    while r != 0:
        a, b = b, r
        r = a % b
    return b

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

def isprime(x):
    t = 1
    for i in range(2, int(x**0.5) + 1):
        if x % i == 0:
            t = 0
            break
    if t == 1 and x != 1:
        return True
    else:
        return False


a, b = map(int, input().split())

CD = divisors(gcd(a, b))

ans = 1
for cd in CD:
    if isprime(cd):
        ans += 1

print(ans)
### BUGGY CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
from collections import Counter
a = list(map(int, input().split()))
c = Counter(a)
s = set()
for k,v in c.items():
    if v>=2:
        s.add(k)
        
a.sort()
tmp = set()
from bisect import bisect_left
while True:
    v = a[0]
    if v*2>a[-1]:
        for item in a:
            tmp.add(item)
        break
    tmp.add(v)
    a = [item for item in a if item%v!=0]
    if not a:
        break

# tmp = [a[0]]
# for i in range(1, n):
#     num = a[i]
# #     for i in range(len(tmp)-1, -1, -1):
#     for i in range(len(tmp)):
#         item = tmp[i]
#         if num%item==0:
#             break
#         if item*2>num:
#             tmp.append(num)
#             break
#     else:
#         tmp.append(num)

tmp = set(tmp) - s
print(len(tmp))

### FIXED CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n = int(input())
from collections import Counter
a = list(map(int, input().split()))
c = Counter(a)
s = set()
for k,v in c.items():
    if v>=2:
        s.add(k)
        
a.sort()
ok = set()
p = set(list(range(1, 10**6+1)))
ck = list(c.keys())
ck.sort()
for num in ck:
    if num in p:
        ok.add(num)
    i = 2
    while num*i<=10**6:
        if num*i in p:
            p.remove(num*i)
        i += 1
tmp = ok
tmp = set(tmp) - s
print(len(tmp))
### BUGGY CODE ###


aord = ord("a")
s = list(raw_input())
k = int(input())
i = 0

while k > 0 and i < len(s):
	if k >= ord('z') - ord(s[i]) + 1:
		if s[i] == "a": continue
		k -= ord('z') - ord(s[i]) + 1
		s[i] = "a"

	i += 1
k = k%26
s[len(s)-1] = chr(ord(s[len(s)-1]) + k)
print ''.join(s)

### FIXED CODE ###


aord = ord("a")
s = list(raw_input())
k = int(input())
i = 0

while k > 0 and i < len(s):
	if k >= ord('z') - ord(s[i]) + 1:
		if s[i] != "a":
			k -= ord('z') - ord(s[i]) + 1
			s[i] = "a"

	i += 1
k = k%26
s[len(s)-1] = chr(ord(s[len(s)-1]) + k)
print ''.join(s)
### BUGGY CODE ###

import sys
read = sys.stdin.read
def main():
    n, *a = map(int, read().split())

    if n == 1:
        print(a[0])
        sys.exit()
    if n == 2:
        print(max(a))
        sys.exit()

    from math import sqrt
    from math import ceil
    maxa = max(a)
    maxa2 = ceil(sqrt(maxa))
    maxa2 = max(6, maxa2)  # maxa2が6未満だとエラーになる
    p = [False if i % 2 == 0 or i % 3 == 0 or i % 5 == 0 else True for i in range(maxa2)]
    p[0] = p[1] = False
    p[2] = p[3] = p[5] = True
    for is1 in range(3, maxa2, 2):
        for is2 in range(is1 ** 2, maxa2, is1):
            p[is2] = False
    prime_list = [i for i, b in enumerate(p) if b]

    r = 1
    jo = []
    for pre in prime_list:
        if all([ae == 1 for ae in a]):
            break
        while True:
            c = [ae % pre == 0 for ae in a]
            if all(c):
                r *= pre
                a = [ae // pre for ae in a]
            else:
                if c.count(0) == 1:
                    r *= pre
                    jo.append(pre)
                    a[c.index(0)] *= pre
                    a = [ae // pre for ae in a]
                else:
                    break
    jo.sort()
    lenjo = len(jo)
    for joe in jo[:lenjo - 1]:
        r = r // joe
    print(r)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
read = sys.stdin.read
from math import gcd
def main():
    n, *a = map(int, read().split())
    if n == 1:
        print(a[0])
        sys.exit()
    l = [0] * (n + 1)
    for i1 in range(n):
        l[i1 + 1] = gcd(l[i1], a[i1])
    r = [0] * (n + 1)
    for j1 in range(n - 1, -1, -1):
        r[j1] = gcd(r[j1 + 1], a[j1])
    m = [0] * (n + 1)
    for k1 in range(n):
        m[k1] = gcd(l[k1], r[k1 + 1])
    r = max(m)
    print(r)

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

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

N = len(S)
M = len(T)


S = [ord(c) for c in S]
T = [ord(c) for c in T]

zzz = ord('-')


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


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


L = maxkobai(N, M)
ret = L
x = [zzz for i in range(L+1)]
#x = ['-'] * (L+1)

for n in range(0, N):
    x[n * (L//N) + 1] = S[n]


for m in range(0, M):
    idx = m * (L // M) + 1
    x_idx = x[idx]
    if not(x_idx == zzz or x_idx == T[m]):
        ret = -1
        break

print(ret)


### FIXED CODE ###

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

N = len(S)
M = len(T)


S = [ord(c) for c in S]
T = [ord(c) for c in T]


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


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


L = maxkobai(N, M)
ret = L
x = dict()

for n in range(0, N):
    x[n * (L//N) + 1] = S[n]


for m in range(0, M):
    idx = m * (L // M) + 1
    tmp = x.get(idx, 0)

    if tmp != T[m] and tmp != 0:
        ret = -1
        break

print(ret)
### BUGGY CODE ###

n= int(input())
s_list= list(input())
r_list=[]
g_list=[]
b_list=[]
count=0
rr,gg,bb=0,0,0
for i in range(0,n):
    if s_list[i]=="R":
        r_list.append(i)
        rr=rr+1
    elif s_list[i]=="G":
        g_list.append(i)
        gg=gg+1
    else:
        b_list.append(i)
        bb=bb+1
sum=rr*gg*bb

for pp in r_list:
    for qq in g_list:
        for rr in b_list:
            if rr-pp == -1*(qq-pp) or rr-pp ==2*(qq-pp) or qq-pp ==2*(rr-pp) :
                count=count+1
print(sum-count)

### FIXED CODE ###

n= int(input())
s_list= list(input())
count=0
rr,bb,gg=0,0,0
for i in range(0,n):
    if s_list[i]=="R":
        rr=rr+1
    elif s_list[i]=="G":
        gg=gg+1
    else:
        bb=bb+1
sum=rr*gg*bb

for p in range(0,n-2):
    for q in range(p+1,n-1):
        if s_list[p] == s_list[q]:
            continue
        elif 2*q-p<n and s_list[2*q-p]!=s_list[p] and s_list[2*q-p]!=s_list[q]:
            count= count+1
print(sum-count)
### BUGGY CODE ###

# E
# This Message Will Self-Destruct in 5s
import numpy as np

N = int(input())
A_list = [int(x) for x in input().split()]
Num_list = np.arange(1,N+1,1)

ans = 0

for i in Num_list:
    for j in range(i+1,N+1):
        if (j-i) == (A_list[j-1] + A_list[i-1]):
            ans += 1

print(ans)

### FIXED CODE ###

from collections import Counter

n=int(input())
a=list(map(int,input().split()))
ans=0
l=[]
r=[]
for i,j in enumerate(a):
    l.append(i+j)
    r.append(i-j)

b=Counter(r)
for i in l:
    ans+=b.get(i,0)

print(ans)
### BUGGY CODE ###

from fractions import gcd
N, M = [int(x) for x in input().split()]
ans = 1
for i in range(M//N, 1, -1):
    rest = M - N*i
    ans = max(ans, gcd(i, rest))
print(ans)


### FIXED CODE ###

from fractions import gcd
N, M = [int(x) for x in input().split()]
ans = 1
d = 1
if (N == 1):
    print(M)
else:
    while (d*d <= M):
        if (M//d * d != M): 
            d += 1
            continue
        d2 = M//d
        if (d*N <= M):
            ans = max(ans, d)
        if (d2*N <= M):
            ans = max(ans, d2)
        d += 1
    print(ans)