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

# -*- coding: utf-8 -*-

import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

# Union-Find木
class UnionFind:
    def __init__(self, n):
        # 親要素のノード番号を格納。par[x] == xの時そのノードは根
        # 1-indexedのままでOK、その場合は[0]は未使用
        self.par = [i for i in range(n+1)]
        # 木の高さを格納する（初期状態では0）
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        # 根ならその番号を返す
        if self.par[x] == x:
            return x
        else:
            # 走査していく過程で親を書き換える
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        # 根を探す
        x = self.find(x)
        y = self.find(y)
        # 木の高さを比較し、低いほうから高いほうに辺を張る
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            # 木の高さが同じなら片方を1増やす
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same(self, x, y):
        return self.find(x) == self.find(y)

N, K, L = map(int, input().split())
uf1 = UnionFind(N)
uf2 = UnionFind(N)
for i in range(K):
    p, q = map(int, input().split())
    uf1.union(p, q)
for i in range(L):
    p, q = map(int, input().split())
    uf2.union(p, q)

ans = [1] * N
for i in range(N):
    for j in range(i+1, N):
        if uf1.same(i+1, j+1) and uf2.same(i+1, j+1):
            ans[i] += 1
            ans[j] += 1
print(*ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-

"""
参考：https://img.atcoder.jp/arc065/editorial.pdf
・Union-Find木
"""

import sys
def input(): return sys.stdin.readline().strip()
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

from collections import Counter

# Union-Find木
class UnionFind:
    def __init__(self, n):
        # 親要素のノード番号を格納。par[x] == xの時そのノードは根
        # 1-indexedのままでOK、その場合は[0]は未使用
        self.par = [i for i in range(n+1)]
        # 木の高さを格納する（初期状態では0）
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        # 根ならその番号を返す
        if self.par[x] == x:
            return x
        else:
            # 走査していく過程で親を書き換える
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        # 根を探す
        x = self.find(x)
        y = self.find(y)
        # 木の高さを比較し、低いほうから高いほうに辺を張る
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            # 木の高さが同じなら片方を1増やす
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # 同じ集合に属するか判定
    def same(self, x, y):
        return self.find(x) == self.find(y)

N, K, L = map(int, input().split())
uf1 = UnionFind(N)
uf2 = UnionFind(N)
for i in range(K):
    p, q = map(int, input().split())
    uf1.union(p, q)
for i in range(L):
    p, q = map(int, input().split())
    uf2.union(p, q)

# (道路グループ番号, 鉄道グループ番号) のペアを各都市について作る
pairs = [None] * N
for i in range(N):
    pairs[i] = (uf1.find(i+1), uf2.find(i+1))

# 同じ内容のペアについて数える
c = Counter(pairs)

ans = [0] * N
for i in range(N):
    # 自分のペアのカウント数を各都市について取得
    ans[i] = c[pairs[i]]
print(*ans)
### BUGGY CODE ###

n, m = map(int, input().split())
a = [int(input()) for x in range(m)]

x = 1
y = 1
for i in range(1, n+1):
  if i in a:
    if i == 1:
      y = 0
    else:
      x = y
      y = 0
  else:
    if i != 1:
      tmp = x + y
      x = y
      y = tmp

print(y % 1000000007)

### FIXED CODE ###

n, m = map(int, input().split())
a = set([int(input()) for x in range(m)])

l = [0]*(n+1)
l[0] = 1

for i in range(1, n+1):
  if i in a:
    l[i] = 0
    continue
  else:
    l[i] = l[i-2] + l[i-1]

print(l[-1] % 1000000007)
### BUGGY CODE ###

N = int(input())
a = list(map(int,input().split()))
if N>2:
    x = [0]*(N-2)
    for i in range(N-2):
        x[i] = a.count(i) + a.count(i+1) + a.count(i+2)
    print(max(x))
elif N == 2:
    if a[0] == a[1] or a[0] == a[1] +1 or a[0] == a[1] -1  :
        print(2)
    else:
        print(1)
else:
    print(1)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
ans = [0]*(10**5+3)

for i in range(N):
    ans[A[i]-1] +=1
    ans[A[i]] +=1
    ans[A[i]+1] +=1

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

n,m=[int(x) for x in input().rstrip().split()]
a=[int(x) for x in input().rstrip().split()]
a.sort(reverse=True)
for i in range(m):
  b,c=[int(x) for x in input().rstrip().split()]
  a.extend([c]*b)
a.sort(reverse=True)
print(sum(a[:n]))


### FIXED CODE ###

n,m=[int(x) for x in input().rstrip().split()]
a=[int(x) for x in input().rstrip().split()]
a.sort(reverse=True)
d=[]
bc=[]
for i in range(m):
  b,c=[int(x) for x in input().rstrip().split()]
  bc.append([b,c])

cnt=0
bc.sort(key=lambda x:x[1],reverse=True)
for b,c in bc:

  d.extend([c]*b)
  cnt+=b
  if n<cnt:
    break
  
d.sort(reverse=True)
a+=d
a.sort(reverse=True)
print(sum(a[:n]))
### BUGGY CODE ###

N = int(input())
P = list(map(int,input().split()))
A = []
ans = 0

for i in range(N):
    A.append(P[i])
    if min(A) == P[i]:
        ans += 1
print(ans)

### FIXED CODE ###

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

cnt = 10**18
ans = 0

for i in range(N):
    if cnt >= P[i]:
        cnt = P[i]
        ans += 1
print(ans)
### BUGGY CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
for _ in range(m):
    a.sort(reverse=True)
    a[0] = a[0] // 2
print(sum(a))

### FIXED CODE ###

from heapq import heapify, heappop, heappush
import math
n, m = map(int, input().split())
a = list(map(int, input().split()))
for i in range(n):
    a[i] = a[i] * -1
heapify(a)
for _ in range(m):
    minval = heappop(a)
    heappush(a, math.ceil(minval / 2))
ans = 0
for i in range(n):
    ans += int(a[i])
print(-ans)
### BUGGY CODE ###

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

for i in range(M):
    B, C = map(int,input().split())
    A_li.extend([C]*B)

A_li.sort()
ans = sum(A_li[-N:])
    
print(str(ans))

### FIXED CODE ###

N, M = map(int,input().split())
A_li = list(map(int,input().split()))
CB_li = []
for i in range(M):
    B,C = map(int,input().split())
    CB_li.append([C,B])

CB_li.sort()
CB_li.reverse()

counter = 0
for i in range(M):
    li = [CB_li[i][0]]*CB_li[i][1]
    A_li.extend(li)
    counter += CB_li[i][1]
    if counter > N:
        break

A_li.sort()
ans = sum(A_li[-N:])
    
print(str(ans))
### BUGGY CODE ###

from collections import deque

S = input()

cands = ["dream", "dreamer", "erase", "eraser"]
searched = {}

queue = deque([""])
find_flag = 0
while len(queue) != 0:
    s = queue.popleft()
#     print(s)
    searched[s] = 1
    if s == S:
        find_flag = 1
        break
        
    s_ = cands[0]
    if (s+s_ == S[:len(s)+len(s_)]) & (not searched.get(s+s_)):
        queue.append(s+s_)

    s_ = cands[1]
    if (s+s_ == S[:len(s)+len(s_)]) & (not searched.get(s+s_)):
        queue.append(s+s_)
        
    s_ = cands[2]
    if (s+s_ == S[:len(s)+len(s_)]) & (not searched.get(s+s_)):
        queue.append(s+s_)
        
    s_ = cands[3]
    if (s+s_ == S[:len(s)+len(s_)]) & (not searched.get(s+s_)):
        queue.append(s+s_)

if find_flag:
    print("YES")
else:
    print("NO")

### FIXED CODE ###

S = input()

candidates = ["dream", "dreamer", "erase", "eraser"]

find_flag = 0
rest_S = S
while True:
#     print(rest_S[-5:], rest_S[-7:]) 
    if len(rest_S) == 0:
        find_flag = 1
        break
    elif (len(rest_S) >= 7) & (rest_S[-7:] in candidates):
        rest_S = rest_S[:-7]
    elif (len(rest_S) >= 6) & (rest_S[-6:] in candidates):
        rest_S = rest_S[:-6]
    elif (len(rest_S) >= 5) & (rest_S[-5:] in candidates):
        rest_S = rest_S[:-5]
    else:
        break

if find_flag:
    print("YES")
else:
    print("NO")
### BUGGY CODE ###

n, q = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n - 1)]
px = [list(map(int, input().split())) for _ in range(q)]

x_sorted = [0 for _ in range(n)]
for i in range(q):
    p = px[i][0]
    x = px[i][1]
    x_sorted[p - 1] += x

start = 0
inf = float('inf')
cost = dict() # コストテーブル
for i, j in ab:
    c = x_sorted[i - 1]
    cost[i - 1] = cost.get(i - 1, []) + [(j - 1, c)]

d = [inf for i in range(n)] # 最短距離
d[start] = 0

qq = [[d[0], 0]]
while qq:
    [du, u] = qq.pop(0) # 最短距離とその頂点
    for v, weight in cost.get(u, []):
        alt = du + weight
        d[v] = alt
        qq.append([alt, v])

ans = ''
for i in range(n):
    ans += str(d[i] + x_sorted[i]) + ' '

print(ans[:-1])


### FIXED CODE ###

from sys import stdin
from collections import defaultdict

if __name__ == '__main__':
    n, q = map(int, stdin.readline().rstrip().split())
    ab = [list(map(int, stdin.readline().rstrip().split())) for _ in range(n - 1)]
    px = [list(map(int, stdin.readline().rstrip().split())) for _ in range(q)]

    g = defaultdict(list)
    for a, b in ab:
        a -= 1
        b -= 1
        g[a].append(b)
        g[b].append(a)

    adder = defaultdict(int)
    for p, x in px:
        p -= 1
        adder[p] += x

    ans = [float('inf')] * n
    ans[0] = adder[0]
    qu = [0]

    while qu:
        cur = qu.pop()

        for target in g[cur]:
            if ans[target] == float('inf'):
                ans[target] = ans[cur] + adder[target]
                qu.append(target)

    for _ans in ans:
        print(_ans)
### BUGGY CODE ###

import itertools

X, Y, Z, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

l = []
for p in itertools.product(A, B, C):
    l.append(sum(p))
l.sort(reverse=True)
for i in range(K):
    print(l[i])

### FIXED CODE ###

x,y,z,k = map(int,input().split())
lisa = list(map(int,input().split()))
lisb = list(map(int,input().split()))
lisc = list(map(int,input().split()))
lisa.sort(reverse=True)
lisb.sort(reverse=True)
lisc.sort(reverse=True)
an = []
ans = []
for num in lisb:
    for nu in lisa:
        an.append(num+nu)
an.sort(reverse=True)
an = an[:min(3001,x*y*z+1)]
for num in lisc:
    for nu in an:
        ans.append(num+nu)
ans.sort(reverse=True)
for i in range(k):
    print(ans[i])
### BUGGY CODE ###

Mx = 9999999999999

H, N = map(int,input().split())
L = [list(map(int,input().split())) for i in range(N)]

D = [Mx] * 40000

D[0] = 0

for i in range(H+1):
    for spell in L:
        if D[i] + spell[1] < D[i+spell[0]]:
            D[i+spell[0]] = D[i] + spell[1]

print(min(D[H:]))

### FIXED CODE ###

import sys
Mx = 999999999

H, N = map(int,sys.stdin.readline().split())
L = [list(map(int,sys.stdin.readline().split())) for i in range(N)]

D = [Mx] * 40000

D[0] = 0

for i in range(H+1):
    for spell in L:
        if D[i] + spell[1] < D[i+spell[0]]:
            D[i+spell[0]] = D[i] + spell[1]

sys.stdout.write(str(min(D[H:])))
### BUGGY CODE ###

if __name__ == '__main__':
    N = int(input())
    A = [int(input()) for _ in range(N)]
    for index in range(N):
        print(max(A[:index] + A[index + 1:]))

### FIXED CODE ###

if __name__ == '__main__':
    N = int(input())
    A = sorted({i: int(input()) for i in range(N)}.items(), key=lambda x: x[1])
    for index in range(N):
        if not A[-1][0] == index:
            print(A[-1][1])
        else:
            print(A[-2][1])
### BUGGY CODE ###

from functools import lru_cache


def solve(n, aaa):
    @lru_cache(maxsize=None)
    def search_min(li, ri, lc, rc):
        w = ri - li
        base = aaa[li] * lc
        if w == 1:
            return base
        lrc = lc + rc
        if w == 2:
            return base + aaa[li + 1] * lrc
        ret = min(search_min(li, i, lc, lrc) + search_min(i, ri, lrc, rc) for i in range(li + 1, ri))
        return ret

    return search_min(0, n - 1, 1, 1) + aaa[-1]


n = int(input())
aaa = list(map(int, input().split()))
print(solve(n, aaa))


### FIXED CODE ###

from functools import lru_cache


def solve(n, aaa):
    @lru_cache(maxsize=None)
    def search_min(li, ri, lc, rc):
        w = ri - li
        base = aaa[li] * lc
        if w == 1:
            return base
        lrc = lc + rc
        if w == 2:
            return base + aaa[li + 1] * lrc
        if w == 3:
            a1, a2 = aaa[li + 1], aaa[li + 2]
            return base + (a1 + a2) * lrc + min(a1 * lc, a2 * rc)
        ret = min(search_min(li, i, lc, lrc) + search_min(i, ri, lrc, rc) for i in range(li + 1, ri))
        return ret

    return search_min(0, n - 1, 1, 1) + aaa[-1]


n = int(input())
aaa = list(map(int, input().split()))
print(solve(n, aaa))
### BUGGY CODE ###

n=int(input())
ps=list(map(float,input().split()))
ans=0
for b in range(2**n):
    if format(b,"b").count("1")>n//2:
        pi=1
        for i in range(n):
            if b & 1:
                pi*=ps[i]
            else:
                pi*=1-ps[i]
            b=b>>1
        ans+=pi
print(ans)

### FIXED CODE ###

n=int(input())
ps=list(map(float,input().split()))
lim=(n+1)//2
dp=[0]*(lim+1)
dp[0]=1
for pi,p in enumerate(ps):
    if pi+1>=lim:
        st=lim-1
        dp[lim]=dp[lim]+dp[lim-1]*p
    else:
        st=pi+1
    for i in range(st,0,-1):
        dp[i]=dp[i-1]*p+dp[i]*(1-p)
    dp[0]=dp[0]*(1-p)
print(dp[-1])
### BUGGY CODE ###

S = input()

p = 2019
N = len(S)
t = [0]*(N+1)
for i in range(N-1,-1,-1):
  
  k = (int(S[i])*pow(10,N-i-1))%p
  t[i] = (t[i+1]+k)%p
t= t[:N]
cnt = [0]*p
for i in range(N):
  cnt[t[i]]+=1
ans = cnt[0]
for i in range(1,p):
  if cnt[i] > 0:
    ans += cnt[i]-1

print(ans)

### FIXED CODE ###

S = input()

p = 2019
N = len(S)
t = [0]*(N+1)
for i in range(N-1,-1,-1):
  k = (int(S[i]) * pow(10,N-i-1,p))%p
  t[i] = (t[i+1]+k)%p
t= t[:N]
cnt = [0]*p
for i in range(N):
  cnt[t[i]]+=1
ans = 0
for i in range(p):
  m = cnt[i]
  if i == 0 and m > 0:
    ans +=  (m*(m+1))//2
  else:
    ans += (m*(m-1))//2
print(ans)
### BUGGY CODE ###

import queue
from collections import deque
import numpy as np
n, x, y = map(int,input().split())
g = [[] for _ in range(n)] 
for i in range(n):
    if i == 0:
        g[i].append(i+1)
    elif i == n-1:
        g[i].append(i-1)
    else:
        g[i].append(i-1)
        g[i].append(i+1)
g[x-1].append(y-1)
g[y-1].append(x-1)

# if n%2==0:
#     ma = int(n/2)
# else:
#     ma = int((n+1)/2)
# print(ma)
d = []
ans = [0]*n
for i in range(n):
    start = i
    dist = [-1] * n
    dist[start] = 0
    # que = queue.Queue()
    # que.put(start)
    q = deque([start])
    while q:
        # v = que.get()
        v = q.popleft()
        for nv in g[v]:
            if dist[nv] != -1:
                continue
            dist[nv] = dist[v]+1
            # que.put(nv)
            q.append(nv)
    for i in dist:
        ans[i] += 1
    # d.append(dist)
# d = np.array(d).flatten()
for i in range(1,n):
    # print(int(np.count_nonzero(d==i)/2))
    print(int(ans[i]/2))


### FIXED CODE ###

def main():
    from collections import deque
    n,x,y=map(int,input().split())
    e=[[]for _ in range(n)]
    for i in range(n-1):
        e[i]+=i+1,
        e[i+1]+=i,
    e[x-1]+=y-1,
    e[y-1]+=x-1,
    a=[0]*n
    for s in range(n):
        d=[-1]*n
        d[s]=0
        q=deque([s])
        add,pop=q.append,q.popleft
        while q:
            v=pop()
            for w in e[v]:
                if d[w]<0:
                    d[w]=d[v]+1
                    add(w)
        for i in d:a[i]+=1
    print(' '.join(str(i//2)for i in a[1:]))
main()
### BUGGY CODE ###

def solve(string):
    h, w, *s = string.split()
    h, w = map(int, [h, w])
    hg = []
    hi = []
    vg = []
    vi = []

    for _s in s:
        gn = 0
        _hi = [0] * w
        _hg = []
        c = 0
        for i, __s in enumerate(_s):
            if __s == "#":
                _hi[i] = -1
                gn += 1
                _hg.append(c)
                c = 0
                continue
            _hi[i] = gn
            c += 1
        _hg.append(c)
        hg.append(_hg)
        hi.append(_hi)
    for _s in zip(*s):
        gn = 0
        _vi = [0] * h
        _vg = []
        c = 0
        for i, __s in enumerate(_s):
            if __s == "#":
                _vi[i] = -1
                gn += 1
                _vg.append(c)
                c = 0
                continue
            _vi[i] = gn
            c += 1
        _vg.append(c)
        vg.append(_vg)
        vi.append(_vi)

    ans = max([max([hg[i][hi[i][j]] + vg[j][vi[j][i]] for j in range(w)]) for i in range(h)])
    return str(ans - 1)


if __name__ == '__main__':
    n, m = map(int, input().split())
    print(solve('{} {}\n'.format(n, m) + '\n'.join([input() for _ in range(n)])))


### FIXED CODE ###

def solve(string):
    h, w, *s = string.split()
    h, w = map(int, [h, w])
    hg = []
    hi = []
    vg = []
    vi = []

    for _s in s:
        gn = 0
        _hi = [0] * w
        _hg = []
        c = 0
        for i, __s in enumerate(_s):
            if __s == "#":
                _hi[i] = -1
                gn += 1
                _hg.append(c)
                c = 0
                continue
            _hi[i] = gn
            c += 1
        _hg.append(c)
        hg.append(_hg)
        hi.append(_hi)
    for _s in zip(*s):
        gn = 0
        _vi = [0] * h
        _vg = []
        c = 0
        for i, __s in enumerate(_s):
            if __s == "#":
                _vi[i] = -1
                gn += 1
                _vg.append(c)
                c = 0
                continue
            _vi[i] = gn
            c += 1
        _vg.append(c)
        vg.append(_vg)
        vi.append(_vi)

    ans = 0
    for i in range(h):
        for j in range(w):
            ans = max(ans, hg[i][hi[i][j]] + vg[j][vi[j][i]])
    return str(ans - 1)


if __name__ == '__main__':
    n, m = map(int, input().split())
    print(solve('{} {}\n'.format(n, m) + '\n'.join([input() for _ in range(n)])))
### BUGGY CODE ###

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

for _ in range(K):
    B = [0] * N
    for i in range(N):
        l = max(0, i - A[i])
        r = min(N - 1, i + A[i])
        B[l] += 1
        if r+1 < N:
            B[r+1] -= 1
    
    for i in range(1, N):
        B[i] += B[i-1]
    
    A = B.copy()
    if min(A) == N:
        break

print(" ".join(map(str, A)))

### FIXED CODE ###

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

for _ in range(K):
    B = [0] * N
    for i, d in enumerate(A):
        l = max(0, i-d)
        r = min(N-1, i+d)
        B[l] += 1
        if r+1 < N:
            B[r+1] -= 1
    
    for i in range(1, N):
        B[i] += B[i-1]
    
    A = B.copy()
    if min(A) == N:
        break

print(" ".join(map(str, A)))
### BUGGY CODE ###

H,W=map(int,input().split())
board=[[True]*(W+2)]
for i in range(H):
    board.append([True]+[a=='#' for a in input()]+[True])
board.append([True]*(W+2))

stack=[]
for i in range(1,H+1):
    for j in range(1,W+1):
        if board[i][j]:
            stack.append([i,j])

cnt=0
while stack:
    nstack=[]
    for h,w in stack:
        if not board[h+1][w]:
            board[h+1][w]=True
            nstack.append([h+1,w])
        if not board[h-1][w]:
            board[h-1][w]=True
            nstack.append([h-1,w])
        if not board[h][w+1]:
            board[h][w+1]=True
            nstack.append([h,w+1])
        if not board[h][w-1]:
            board[h][w-1]=True
            nstack.append([h,w-1])

    stack=nstack
    cnt+=1

print(cnt-1)

### FIXED CODE ###

H,W=map(int,input().split())
board=[[True]*(W+2)]
for i in range(H):
    board.append([True]+[a=='#' for a in input()]+[True])
board.append([True]*(W+2))

q=[]
for h in range(1,H+1):
    for w in range(1,W+1):
        if board[h][w]:
            q.append((h,w))

cnt=0
while q:
    nq=[]
    for h,w in q:
        if not board[h+1][w]:
            board[h+1][w]=True
            nq.append((h+1,w))
        if not board[h-1][w]:
            board[h-1][w]=True
            nq.append((h-1,w))
        if not board[h][w+1]:
            board[h][w+1]=True
            nq.append((h,w+1))
        if not board[h][w-1]:
            board[h][w-1]=True
            nq.append((h,w-1))

    q=nq
    cnt+=1

print(cnt-1)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
from bisect import bisect_left


## 約数の列挙O(N)
def divisor(n): #nの約数を全て求める
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return table

def solve(N: int, M: int):
    max_answer = M//N
    divisors = divisor(M)
    divisors.sort()
    for m in range(max_answer,0,-1):
        index = bisect_left(divisors,m)
        if divisors[index] == m:
            print(m)
            return 

    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    solve(N, M)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from bisect import bisect_left


## 約数の列挙O(N)
def divisor(n): #nの約数を全て求める
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return table

def solve(N: int, M: int):
    if M%N == 0:
        print(M//N)
        return

    max_answer = M//N
    divisors = divisor(M)
    divisors.sort()

    index = bisect_left(divisors,max_answer)
    if index == 0:
        print(1)
        return 
    print(divisors[index-1])


    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    M = int(next(tokens))  # type: int
    solve(N, M)

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

from collections import defaultdict
def main():
    def f(n):
        if n == 0:
            return 0
        if d[n] != 0:
            return d[n]
        d[n] = f(n % sum(list(map(int, bin(n)[2:])))) + 1
    def rev(i):
        nonlocal c, X
        if X[i] == '0':
            c += 1
            X[i] = '1'
        else:
            c -= 1
            X[i] = '0'


    n = int(input())
    X = list(input())
    d = defaultdict(int)
    d[0] = 0
    printl = lambda x, y: print(d[x % y] + 1 if x != 0 else 0)
    for i in range(1, n):
        f(i)
    c = sum(list(map(int, X)))
    rev(0)
    m = int(''.join(X), 2)
    printl(m, c)
    for i in range(n - 1):
        rev(i)
        rev(i + 1)
        m = int(''.join(X), 2)
        printl(m, c)





if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    def f(n):
        if n == 0: return 0
        return f(n % bin(n).count('1')) + 1
    n = int(input())
    X = list(input())
    c = sum(list(map(int, X)))
    m = int(''.join(X), 2)
    mp, mm = m % (c + 1), m % (c - 1) if c - 1 != 0 else 0
    jp, jm = 1, 1
    ans = [0] * n
    for i in range(n - 1, -1, -1):
        if X[i] == '0':
            mod = c + 1
            ans[i] = f((mp + jp) % mod) + 1
        else:
            ans[i] = f((mm - jm + mod) % mod) + 1 if (mod := c - 1) != 0 else 0
        jp, jm = (jp << 1) % (c + 1), (jm << 1) % (c - 1) if c - 1 != 0 else 0
    [print(a) for a in ans]
if __name__ == '__main__':
    main()
### BUGGY CODE ###

n = int(input())
A = list(map(int, input().split()))
l = []
f = 0
for a in A:
  if a in l:
    f = 1
    print("NO")
    break
  else:
    l.append(a)
if f == 0:
  print("YES")

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
B = list(set(A))
if len(A) == len(B):
  print("YES")
else:
  print("NO")
### BUGGY CODE ###

R,G,B,N = map(int,input().split())
RGB = list(reversed(sorted([R,G,B])))
MAXES = [N//i for i in RGB]
answer = 0
for i in range(MAXES[0]+1):
    for j in range(MAXES[1]+1):
        for k in range(MAXES[2]+1):
            if RGB[0]*i + RGB[1]*j + RGB[2]*k == N:
                answer += 1
print(answer)

### FIXED CODE ###

R,G,B,N = map(int, input().split())
answer = 0
for i in range(N+1):
    for j in range(N+1):
        if N>=(i*R+j*G) and  (N-(i*R+j*G))%B==0:
            answer += 1
print(answer)