Harryxun/stf_run huggingface dataset:
import sys,math,bisect
input = sys.stdin.readline

mod = 1000000007
eps = 0.000001

n = int(input())

ab = []
ang = []
for i in range(n):
    a,b = map(int,input().split())
    ab.append((a,b))
    if a == 0:
        ang.append((90.0,i))
    else:
        ang.append((math.degrees(math.atan(b/a)),i))
ang.sort()

res = 1
used = [False]*n


rest = n

for i in range(n):
    e,idx = ang[i]
    if used[idx]:
        continue
    used[idx] = True
    if e > eps:
        break
    
    cnt = 1
    k = i + 1
    while k < n:
        if abs(e-ang[k][0]) <= eps:
            p = ang[k][1]
            if ab[p][0]*ab[idx][1] == ab[p][1]*ab[idx][0]:
                cnt += 1
                used[p] = True
            k += 1
        else:
            break


    cnt2 = 0

    ok = n-1
    ng = i+1
    while ok-ng > 1:
        mid = (ok+ng)//2
        if ang[mid][0] >= e+90-eps:
            ok = mid
        else:
            ng = mid

    k = ok
    while k < n:
        if abs(e+90-ang[k][0]) <= 0.000002:
            p = ang[k][1]
            if ab[p][0]*ab[idx][0] + ab[p][1]*ab[idx][1] == 0:
                cnt2 += 1
                used[p] = True
            k += 1
        else:
            break

    if cnt2 != 0:
        res = res*(pow(2,cnt,mod) + pow(2,cnt2,mod) - 1)%mod
        rest -= cnt+cnt2

res = res*pow(2,rest,mod)%mod - 1
print(res)





### FIXED CODE ###

import sys,math
input = sys.stdin.buffer.readline

mod = 1000000007
n = int(input())

ab = []
ang = dict()
rev = dict()
dg = 10**20
zero = 0

for i in range(n):
    a,b = map(int,input().split())
    if a == 0 and b == 0:
        zero += 1
    elif a == 0:
        if 1 in ang:
            ang[1] += 1
        else:
            ang[1] = 1
    elif b == 0:
        if 1 in rev:
            rev[1] += 1
        else:
            rev[1] = 1
    elif a*b > 0:
        if a < 0 and b < 0:
            a,b = -a,-b
        g = math.gcd(a,b)
        a,b = a//g,b//g

        if a*dg + b in ang:
            ang[a*dg + b] += 1
        else:
            ang[a*dg + b] = 1
    else:
        a,b = abs(a),abs(b)
        g = math.gcd(a,b)
        a,b = a//g,b//g

        if b*dg + a in rev:
            rev[b*dg + a] += 1
        else:
            rev[b*dg + a] = 1

rest = n - zero

res = 1

for e in ang:
    if e in rev:
        res = res*(pow(2,ang[e],mod) + pow(2,rev[e],mod) - 1)%mod
        rest -= ang[e] + rev[e]

res = res*pow(2,rest,mod)%mod - 1 + zero

print(res%mod)
w,h,x,y=map(int,input().split())

if w/x==2 and h/y==2:
    print(w*h/2,'1')
else:
    print(w*h/2,'0')

### FIXED CODE ###

w,h,x,y=map(int,input().split())

if x==0 or y==0:
    print(w*h/2,'0')
elif w/x==2 and h/y==2:
    print(w*h/2,'1')
else:
    print(w*h/2,'0')
L,R = map(int,input().split())

# Rが2019未満のとき
if R < 2019 :
    print((L * (L + 1)) % 2019)
# 範囲内に2019を含む時
elif L <= 2019 and R >= 2019 :
    print(0)
# LもRも2019より高い場合
else :
    R = min(R, L + 2018)
    ans = 2018
    for i in range(L,R + 1):
        b = i + 1
        for j in range(b,R + 1):
            x = (i * j) % 2019
            ans = min(ans, x)
    print(ans)


### FIXED CODE ###

N,A,B = map(int,input().split())
if N * A < B :
    print(N * A)
else :
    print(B)
h, w = map(int, input().split())
a = [input() for _ in range(h)]
memo_yoko = [False]*w
memo_tate = [False]*h
for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            memo_yoko[i] = True
            memo_tate[j] = True
for i in range(h):
    if memo_yoko[i]:
        for j in range(w):
            if memo_tate[j]:
                print(a[i][j], end="")
        print()

### FIXED CODE ###

h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]
memo_yoko = []
memo_tate = []
for i in range(h):
    if "#" in a[i]:
        memo_yoko.append(i)

for j in range(w):
    if any(a[i][j] == "#" for i in range(h)):
        memo_tate.append(j)
#print(memo_yoko)
#rint(memo_tate)
for i in memo_yoko:
    for j in memo_tate:
        print(a[i][j], end="")
    print()
import sys
import numpy as np
input = sys.stdin.readline
 
MOD = 10**9 + 7
U = 2 ** 20
 
N = int(input())
A = [int(x) for x in input().split()]
C = np.zeros(N,dtype = np.int64) # cumsum
 
arr = np.zeros((U,2),dtype=np.int64)
arr[:,0] = 1
 
zero_update = np.zeros(U,dtype=np.int64) #0が出てきて更新した回数
zero_cnt = 0
 
c = 0
for a in A:
  c ^= a
  if c == 0:
    zero_cnt += 1
    continue
  n = zero_cnt - zero_update[c]
  zero_update[c] = zero_cnt
  a = arr[c,0]
  b = arr[c,1]
  a,b = a+n*b,b
  a,b = a,a+b
  a %= MOD
  b %= MOD
  arr[c,0] = a
  arr[c,1] = b
 
answer = 0
final = C[-1]
if final != 0:
  answer = arr[final,0]
else:
  answer = arr[1:,1].sum()
  answer += pow(2,zero_cnt-1,MOD)
  answer %= MOD
print(answer)


### FIXED CODE ###

import sys
input = sys.stdin.readline
 
MOD = 10**9 + 7
U = 2 ** 20
 
N = int(input())
A = [int(x) for x in input().split()]
 
arr_0 = [1] * U
arr_1 = [0] * U
 
zero_update = [0] * U #0が出てきて更新した回数
zero_cnt = 0
 
c = 0
for a in A:
  c ^= a
  if c == 0:
    zero_cnt += 1
    continue
  n = zero_cnt - zero_update[c]
  zero_update[c] = zero_cnt
  a = arr_0[c]
  b = arr_1[c]
  a,b = a+n*b,b
  a,b = a,a+b
  a %= MOD
  b %= MOD
  arr_0[c] = a
  arr_1[c] = b
 
answer = 0
if c != 0:
  answer = arr_0[c]
else:
  answer = sum(arr_1[1:])
  answer += pow(2,zero_cnt-1,MOD)
  answer %= MOD
print(answer)
N = int(input())
S = input()
K = int(input())
print("".join([i for i in S if i==S[K-1] else "*"]))

### FIXED CODE ###

N = int(input())
S = input()
K = int(input())
print("".join([i if i==S[K-1] else "*" for i in S]))
def main():
    A, B, K = map(int, input().split())
    r = set()
    for i in range(A, A + K):
        r.add(i)

    for i in range(B, B - K, -1):
        r.add(i)
    O = list(r).sort()
    for o in O:
        print(o)


main()


### FIXED CODE ###

def main():
    A, B, K = map(int, input().split())
    r = set()
    for i in range(A, A + K):
        if A <= i and B >= i:
            r.add(i)

    for i in range(B, B - K, -1):
        if A <= i and B >= i:
            r.add(i)
    O = list(r)
    O.sort()
    for o in O:
        print(o)


main()
N,K = map(int,input().split())
A = list(map(int,input().split()))
L = []
for i in range(N):
    for j in range(1,N+1):
        if i > j - 1:
            continue
        else:
            l = A[i:j]
            L.append(sum(l))
L = list(set(L))
def combinationListRecursive(data, r):
  if r == 0 or r > len(data):
    return []

  result = []
  _combinationListRecursive(data, r, 0, [], result)
  return result


def _combinationListRecursive(data, r, start, progress, result):
  if r == 0:
    result.append(progress)
    return

  for i in range(start, len(data)):
    _combinationListRecursive(data, r - 1, i + 1, progress + [data[i]], result)
result = combinationListRecursive(L,K)
ans_list = []
for list_c in result:
    for e in list_c:
        if e == list_c[0]:
            copy = e
            continue
        AND = copy & e
        if e == list_c[-1]:
            ans = AND
            ans_list.append(ans)
            break
        copy = AND
print(max(ans_list))

### FIXED CODE ###

def debug():
    import itertools
    N,K = map(int,input().split())
    a = list(map(int,input().split()))
    beauty = []
    for i in range(N):
        for j in range(i+1,N+1):
            part = a[i:j]
            beauty.append(sum(part))
    choise = [e for e in itertools.combinations(beauty,K)]
    ans = 0
    for pair in choise:
        res = pair[0]
        for i in range(1,len(pair)):
            res = res & pair[i]
        if res > ans :
            ans = res
            adopt = pair
    print(ans)
    print(pair)
    print(sorted(beauty))

def main():
    N,K = map(int,input().split())
    a = list(map(int,input().split()))
    degit = sum(a).bit_length()
    beaty = []
    manage = [[] for i in range(degit)]
    for i in range(N):
        for j in range(i+1,N+1):
            part_sum = sum(a[i:j])
            manage[part_sum.bit_length()-1].append(part_sum)
    
    candidate = []
    for i in range(degit-1,-1,-1):
        if len(manage[i]) >= K:
            candidate = manage[i]
            note = i
            break

    for i in range(note,-1,-1):
        final = []
        judge = pow(2,i)
        for e in candidate:
            if judge == judge & e:
                final.append(e)
        if len(final) == K:
            break
        elif len(final) > K:
            candidate = final
        if i == 0:
            final = candidate[:K]

    ans = final[0]
    for i in range(1,K):
        ans = ans & final[i]
    print(ans)    
main()
a, b, k = map(int, input().split())


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)

    divisors.sort()
    return divisors


a_div = make_divisors(a)
b_div = make_divisors(b)
div_list = a_div + b_div

ans = [x for x in set(div_list) if div_list.count(x) > 1]

print(sorted(ans[-k]))

### FIXED CODE ###

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


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)

    divisors.sort()
    return divisors


a_div = make_divisors(a)
b_div = make_divisors(b)
div_list = a_div + b_div

ans = sorted([x for x in set(div_list) if div_list.count(x) > 1])

print(ans[-k])
import queue

dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
H, W = map(int, input().split())
field = [input() for _ in range(H)]

dist = [[-1] * W for _ in range(W)]
que = queue.Queue()
que.put((0, 0))
dist[0][0] = 0

while not que.empty():
  y, x = que.get()
  if y == H - 1 and x == W - 1:
    break
  for i in range(4):
    ny, nx = y + dy[i], x + dx[i]
    if nx < 0 or nx >= W or ny < 0 or ny >= H:
      continue
    if field[ny][nx] == '#':
      continue
    if dist[ny][nx] != -1:
      continue
    dist[ny][nx] = dist[y][x] + 1
    que.put((ny, nx))
    
count = sum([f.count('#') for f in field])
      
if dist[H - 1][W - 1] != -1:
  print(H * W - count - dist[H - 1][W - 1] - 1)
else:
  print(-1)

### FIXED CODE ###

from collections import deque

R,C = list(map(int,input().split()))
Sx,Sy = 0,0
Gx,Gy = R-1,C-1
Mize = [input() for _ in range(R)]
dd = [[1, 0], [-1, 0], [0, 1], [0, -1]]

def bfs():
    d = [[float('inf')] * C for i in range(R)]
    q = deque([])
    d[Sx][Sy] = 0
    q.append((Sx,Sy))
    while(len(q) != 0):
        x,y = q.popleft()
        if x == Gx and y == Gy:
            break
        for dx,dy in dd:
            
            if -1<x+dx<R and -1<y+dy<C and Mize[x+dx][y+dy]=='.' and d[x+dx][y+dy] == float('inf'):
                q.append([x+dx,y+dy])
                d[x+dx][y+dy] = d[x][y] + 1
    return d[Gx][Gy]

white = sum([m.count('#') for m in Mize])
need = bfs()
if need == float('inf'):
    print(-1)
else:
    print(R*C-white-need-1)
#!/usr/bin/env python3
import sys
from itertools import takewhile, count


def solve(N: int, K: int):
    return max(takewhile(lambda i: N > (K ** i), count(1))) + 1

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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
    K = int(next(tokens))  # type: int
    print(solve(N, K))

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
from itertools import takewhile, count


def solve(N: int, K: int):
    return max(takewhile(lambda i: N >= (K ** i), count(0))) + 1

# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
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
    K = int(next(tokens))  # type: int
    print(solve(N, K))

if __name__ == '__main__':
    main()
s, w = map(int, input().split())
print("unsafe" s <= w else "safe")

### FIXED CODE ###

s, w = map(int, input().split())
print("safe" if s > w else "unsafe")
n, k = map(int, input().split())
sunukes = [list(map(int, input().split())) for i in range(k*2)]

names = list(range(1,n+1))
print(sunukes)
for i in range(0,k+2,2):
  syoji = sunukes[i]
  okashi = sunukes[i+1]
  print(syoji,okashi)
  for n in okashi:
    if n in names:
      names.remove(n)

print(len(names))

### FIXED CODE ###

n, k = map(int, input().split())
sunukes = [list(map(int, input().split())) for i in range(k*2)]

names = list(range(1,n+1))
for i in range(0,k):
  j = i*2
  syoji = sunukes[j]
  okashi = sunukes[j+1]
  for n in okashi:
    if n in names:
      names.remove(n)

print(len(names))
import math

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

if n == 1 or k == 1:
	print(1)
else:
	print(math.gcd(n, k))

### FIXED CODE ###

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

if n >= k:
    n %= k

print(min(n, k-n))
n,m = [int(i) for i in input().split()]
e = [[int(i) for i in input().split()] for i in range(n)]
e.sort()
#print(n,m,e)
#e=dict(e)
#print(n,m,e,e[0][0]*m)

total=0
if m < e[0][1]:
  total=e[0][0]*m
else:
  tmp=e[0][0]*e[0][1]
  m-=e[0][1]


#print(m)  
flag=0
for i in range(1,n):
  if 0 <= m <e[i][1] and flag==0:
    flag=1
    total=tmp+e[i][0]*m
  tmp+=e[i][0]*e[i][1]
  m-=e[i][1]

if n==1:
  total=e[0][0]*e[0][1]


print(total)

### FIXED CODE ###

n,m = [int(i) for i in input().split()]
e = [[int(i) for i in input().split()] for i in range(n)]
e.sort()
#print(n,m,e)

total=0
for i in range(n):
    if m > 0:
      total+=e[i][0]*min(e[i][1],m)
    m-=e[i][1]
    
print(total)
from fractions import gcd
from functools import reduce

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

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

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

lcm = lcm_list(A)
S = 0
for i in range(N):
    S += lcm // A[i]

print(round(S % (1e9 + 7)))

### FIXED CODE ###

import sys
from fractions import gcd
from functools import reduce

sys.setrecursionlimit(2147483647)

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

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

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

    lcm = lcm_list(A)
    S = 0
    for i in range(N):
        S += lcm // A[i]

    print(round(S % (round(1e9) + 7)))

main()
x = input()


if x < 1200:
    print("ABC")
else:
    print("ARC")

### FIXED CODE ###

x = int(input())


if x < 1200:
    print("ABC")
else:
    print("ARC")
N, M = list(map(int, input().split(' ')))

root = [[] for i in range(M+1)]
for i in range(M):
  A, B = list(map(int, input().split(' ')))
  root[A].append(B)
  root[B].append(A)

mitisurube = [-1 for i in range(N+1)]
cost = [-1 for i in range(N+1)]
next_ = [1]
cost[1] = 0

while next_:
  now_pos = next_.pop(0)
  for next_pos in root[now_pos]:
    if cost[next_pos] == -1 or cost[next_pos] > cost[now_pos] + 1:
      cost[next_pos] = cost[now_pos] + 1
      mitisurube[next_pos] = now_pos
      next_.append(next_pos)
#print('root')
#print(*root)
#print('cost')
#print(*cost)
#print('mitisirube')
if mitisurube.count(-1) < 3:
  print('Yes')
  print(*mitisurube[2:], sep='\n')
else:
  print('No')

### FIXED CODE ###

from collections import deque

def main():
  N, M = list(map(int, input().split(' ')))

  root = [[] for i in range(N+1)]
  for i in range(M):
    A, B = list(map(int, input().split(' ')))
    root[A].append(B)
    root[B].append(A)

  mitisurube = [-1 for i in range(N+1)]
  next_ = deque()
  next_.append(1)

  while next_:
    now_pos = next_.popleft()
    for next_pos in root[now_pos]:
      if mitisurube[next_pos] == -1:
        mitisurube[next_pos] = now_pos
        next_.append(next_pos)
  #print('root')
  #print(*root)
  #print('mitisirube')
  print('Yes')
  print(*mitisurube[2:], sep='\n')

if __name__ == '__main__':
  main()
S = input()
if(S = "AAA" or S = "BBB"):
  print("No")
else:
  print("Yes")

### FIXED CODE ###

S = input()
if(S == "AAA" or S == "BBB"):
  print("No")
else:
  print("Yes")
from collections import deque


ans = {1:1}

def dfs(tree,nodes):
    for node in nodes:
        nexts = tree[node]
        for next,l in nexts.items():
            if l% 2 == 0 :
                ans[next] = ans[node]
            else:
                ans[next] = 1 - ans[node]
            tree[next].pop(node)

        dfs(tree,nexts)

    return 0




if __name__ == "__main__":
    tree= {}
    N = int(input())
    if N == 1:
        u, v, w = list(map(int, input().split(" ")))
        if w %2 == 1:
            print(1)
            print(0)
        else:
            print(0)
            print(0)
    else:
        for i in range(N-1):
            u,v,w = list(map(int,input().split(" ")))

            if u not in tree:
                tree[u] = {}
            tree[u][v] = w

            if v not in tree:
                tree[v] = {}
            tree[v][u] = w
            dfs(tree,[1])
            for i in range(1,N+1):
                print(ans[i])


### FIXED CODE ###

from collections import deque
import sys

sys.setrecursionlimit(50000000)


ans = {1: 1}


def dfs(tree, nodes):
    for node in nodes:
        nexts = tree[node]
        for next, l in nexts.items():
            if l % 2 == 0:
                ans[next] = ans[node]
            else:
                ans[next] = 1 - ans[node]
            tree[next].pop(node)

        dfs(tree, nexts)

    return 0


if __name__ == "__main__":
    tree = {}
    N = int(input())
    if N == 1:
        u, v, w = list(map(int, input().split(" ")))
        if w % 2 == 1:
            print(1)
            print(0)
        else:
            print(0)
            print(0)
    else:
        for i in range(N - 1):
            u, v, w = list(map(int, input().split(" ")))

            if u not in tree:
                tree[u] = {}
            tree[u][v] = w

            if v not in tree:
                tree[v] = {}
            tree[v][u] = w
        dfs(tree, [1])
        for i in range(1, N + 1):
            print(ans[i])
a, b, c, d = list(map(int, input().split()))
A = a - d
B = c - b
if A>=B:
  print('Yes')
else:
  print('No')

### FIXED CODE ###

s, w = map(int, input().split())
if w>=s:
    print("unsafe")
else:
    print("safe")
N=int(raw_input())

A = [0 for i in range(N)]

for i in range(N):
    a=int(raw_input())
    A[a-1]=(A[a-1]+1)%2

print sum(A)

### FIXED CODE ###

N=int(raw_input())
A = []
for i in range(N):
    A.append(int(raw_input()))

A.sort()
prev=A[0]
count=1
all_count=0
for i in range(1,N):
    if prev==A[i]:
        count+=1
    else:
        prev=A[i]
        all_count+=count%2
        count=1
all_count+=count%2

print all_count
#d=["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]
#import numpy as np
#import math
#n=int(input())
#li=input().split()
#S=input()
#lis=list(map(int,input().split()))
import fractions
l=[]
n=int(input())
for i in range(n):
    l.append(int(input()))
ans=l[0]
for i in range(n-1):
    a=int((ans*l[i+1])/fractions.gcd(ans,l[i+1]))
    ans=a
print(ans)


### FIXED CODE ###

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

from fractions import gcd
lcm=1
for i in range(n):
    lcm=(lcm*t[i])//gcd(lcm,t[i])
print(lcm)
#input
N, W = map(int, input().split())
w = [0] * N
v = [0] * N
for i in range(N):
    w[i], v[i] = map(int, input().split())

#output
import numpy as np
V = max(v)
INF = 10**6
dp = np.zeros((N+1, N*V+1), int)
dp[0] = INF
dp[0, 0] = 0

for i in range(N):
    for j in range(N*V+1):
        if j < v[i]:
            dp[i+1, j] = dp[i, j]
        else:
            dp[i+1, j] = min(dp[i, j], dp[i, j-v[i]] + w[i])

answer = 0
for i in range(N*V+1):
    if dp[N, i] <= W:
        answer = i

print(answer)

### FIXED CODE ###

#input
N, W = map(int, input().split())
w = [0] * N
v = [0] * N
for i in range(N):
    w[i], v[i] = map(int, input().split())

#output
import numpy as np
V = max(v)
INF = 10**10
dp = np.full((N+1, N*V+1), INF)
dp[0, 0] = 0

for i in range(N):
    dp[i+1, v[i]:] = np.minimum(dp[i, v[i]:], dp[i, :-v[i]]+w[i])
    dp[i+1, :v[i]] = dp[i, :v[i]]

answer = 0
for i in range(N*V+1):
    if dp[N, i] <= W:
        answer = i

print(answer)
n, k = list(map(int,input().split()))
a = list(map(int,input().split()))
 
position = 1
exp = [1]
count = 0
 
if n >= k:
  for i in range(k):
    position = a[position - 1]
  print(position)
else:
  for i in range(k):
    position = a[position - 1]
    count += 1
    if position in exp:
      exp.append(position)
    else:
      break
  init = exp.index(position)
  res = (k - init) % (count - init)
  print(exp[init + res])

### FIXED CODE ###

n, k = list(map(int,input().split()))
a = list(map(int,input().split()))
 
position = 1
exp1 = [0] * n
exp1[0] = 1
exp = [1]
count = 0
 
if n >= k:
  for i in range(k):
    position = a[position - 1]
  print(position)
else:
  for i in range(k):
    position = a[position - 1]
    count += 1
    if exp1[position - 1] == 0:
      exp.append(position)
      exp1[position - 1] += 1
    else:
      break
  init = exp.index(position)
  res = (k - init) % (count - init)
  print(exp[init + res])
def main()->None:
    # gridの処理
    # 近傍の座標をdx=[-1,0,1], dy=[-1,0,1]を用いて
    # (xx, yy) が　xx = x + dx , yy = y + dy　とできる
    # 参考：http://prd-xxx.hateblo.jp/entry/2017/10/19/205331
    # 入力のグリッドから一点ずつ座標指定して選んでその周囲８マスを調べる。
    H, W = map(int, input().split())
    src = [input() for _ in range(H)]
    ans = []
    for row in src:
        ans.append(list(row))


    dxdy = [(-1,-1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
    for y in range(H):
        for x in range(W):
            if src[y][x] == "#":continue
            c = 0
            for dx, dy in dxdy:
                # 探索範囲はx:0~W, y:0~Hでその周囲８マスを探索する
                if x+dx < 0 or x+dx > W-1 or y+dy < 0 or y+dy > H-1: continue
                if src[y+dy][x+dx] == "#": c += 1
        ans[y][x] = c
    
    for row in ans:
        print("".join(list(map(str, row))))




if __name__ == "__main__":
    main()

### FIXED CODE ###



def main()->None:
    # gridの処理
    # 近傍の座標をdx=[-1,0,1], dy=[-1,0,1]を用いて
    # (xx, yy) が　xx = x + dx , yy = y + dy　とできる
    # 参考：http://prd-xxx.hateblo.jp/entry/2017/10/19/205331
    # 入力のグリッドから一点ずつ座標指定して選んでその周囲８マスを調べる。
    H, W = map(int, input().split())
    src = [input() for _ in range(H)]
    ans = []
    for row in src:
        ans.append(list(row))


    dxdy = [(-1,-1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1)]
    for y in range(H):
        for x in range(W):
            if src[y][x] == "#":continue
            c = 0
            for dx, dy in dxdy:
                # 探索範囲はx:0~W, y:0~Hでその周囲８マスを探索する
                if x+dx < 0 or x+dx > W-1 or y+dy < 0 or y+dy > H-1: continue
                if src[y+dy][x+dx] == "#": c += 1
            ans[y][x] = c
    
    for row in ans:
        print("".join(list(map(str, row))))


if __name__ == "__main__":
    main()
N, K = map(int, input().split())
A = list(map(int, input().split()))


def f(n):
    cnt = 0
    for a in A:
            # a/nが偶数の場合
        if a % n == 0:
            cnt += a//(n-1)
        # a/nが奇数の場合
        else:
            cnt += a//n
    return True if K >= cnt else False


l = 0
r = max(A)
# 二分探索
while r - l > 1:
    m = (r+l)//2
    if f(m):
        r = m
    else:
        l = m
print(r)


### FIXED CODE ###

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


def f(n):
    cnt = 0
    for a in A:
            # a/nが偶数の場合
        if a % n == 0:
            cnt += a//n-1
        # a/nが奇数の場合
        else:
            cnt += a//n
    return True if K >= cnt else False


l = 0
r = max(A)
# 二分探索
while r - l > 1:
    m = (r+l)//2
    if f(m):
        r = m
    else:
        l = m
print(r)