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

from collections import deque

# 伸ばせる限り伸ばせば答

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

graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

path = deque(AB[0])
visited = set(AB[0])

while True:
    x = path[0]
    update = False
    for y in graph[x]:
        if y not in visited:
            path.appendleft(y)
            visited.add(y)
            update = True
            break
    if not update:
        break
while True:
    x = path[-1]
    update = False
    for y in graph[x]:
        if y not in visited:
            path.append(y)
            visited.add(y)
            update = True
            break
    if not update:
        break

print(len(path))
print(*path)

### FIXED CODE ###

import sys
input = sys.stdin.readline

from collections import deque

# 伸ばせる限り伸ばせば答

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

graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

path = deque(AB[0])
visited = set(AB[0])

while True:
    x = path[0]
    update = False
    for y in graph[x]:
        if y not in visited:
            path.appendleft(y)
            visited.add(y)
            update = True
            break
    if not update:
        break
while True:
    x = path[-1]
    update = False
    for y in graph[x]:
        if y not in visited:
            path.append(y)
            visited.add(y)
            update = True
            break
    if not update:
        break

print(len(path))
print(*path)
def third_root(q):
    x=q/2
    while abs(x**3-q)>=q*10**(-5):
        x=x-(x**3-q)/(3*x**2)
    return x
while 1:
    q=input()
    if q==-1:break
    ans=third_root(q)
    print(ans)

### FIXED CODE ###

def third_root(q):
    x=q/2
    while abs(x**3-q)>=q*10**(-5):
        x=x-(x**3-q)/(3*x**2)
    return x
while 1:
    q=eval(input())
    if q==-1:break
    ans=third_root(q)
    print(ans)
S = input()
K = int(input())

if S[0] != S[-1]:
    ans = 0
    for i in range(len(S) - 1):
        if S[i] == S[i + 1]:
            S = S[:i] + '*' + S[i + 2:]
            ans += 1
    print(ans * K)
else:
    # S -> s_1 s_2 ... s_k + A + t_l t_l-1 ... t_1 (s_i = t_j)と分解
    k, l = 0, len(S) - 1
    while k < len(S) and S[k] == S[-1]:
        k += 1
    while l > -1 and S[l] == S[0]:
        l -= 1

    # 連結に関係ない部分のカウント
    A = S[k:l + 1]
    ans = 0
    for i in range(len(A) - 1):
        if A[i + 1] == A[i]:
            A = A[:i + 1] + '*' + A[i + 2:]
            ans += 1
    ans *= K

    # 連結に関係ある部分のカウント
    if l == -1 and k == len(S):
        # 全部同じ
        print((len(S) * K) // 2)
    else:
        ans += (len(S) - l + k - 1) // 2 * (K - 1)
        ans += (len(S) - l) // 2 + (k - 1) // 2
        print(ans)


### FIXED CODE ###

S = input()
K = int(input())

if S[0] != S[-1]:
    ans = 0
    for i in range(len(S) - 1):
        if S[i] == S[i + 1]:
            S = S[:i + 1] + '*' + S[i + 2:]
            ans += 1
    print(ans * K)
else:
    # S -> s_1 s_2 ... s_k + A + t_l t_l-1 ... t_1 (s_i = t_j)と分解
    k, l = 0, len(S) - 1
    while k < len(S) and S[k] == S[-1]:
        k += 1
    while l > -1 and S[l] == S[0]:
        l -= 1

    # 連結に関係ない部分のカウント
    A = S[k:l + 1]
    ans = 0
    for i in range(len(A) - 1):
        if A[i + 1] == A[i]:
            A = A[:i + 1] + '*' + A[i + 2:]
            ans += 1
    ans *= K

    # 連結に関係ある部分のカウント
    if l == -1 and k == len(S):
        # 全部同じ
        print((len(S) * K) // 2)
    else:
        ans += (len(S) - l + k - 1) // 2 * (K - 1)
        ans += (len(S) - l - 1) // 2 + k // 2
        print(ans)
n,m=map(int, input().split())
e=[[] for _ in range(n)]
e_rev=[[] for _ in range(n)]
for i in range(m):
    ai,bi=map(int, input().split())
    e[ai].append(bi)
    e_rev[bi].append(ai)

p_ord=[]
used=[0]*n
def dfs(v):
    used[v]=1
    for u in e[v]:
        if not used[u]:
            dfs(u)
    p_ord.append(v)
for i in range(n):
    if not used[i]:
        dfs(i)
compo = [0]*n
used=[0]*n
def dfs_rev(v,c):
    compo[v]=c
    used[v]=1
    for u in e_rev[v]:
        if not used[u]:
            dfs_rev(u,c)
cnt=0
for i in reversed(p_ord):
    if not used[i]:
        dfs_rev(i,cnt)
        cnt+=1
cc=[[] for _ in range(cnt+1)]
for i in range(n):
    cc[compo[i]].append(i)
print(len(cc))
for cci in cc:
    print(len(cci),*cci)

### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)
n,m=map(int, input().split())
e=[[] for _ in range(n)]
e_rev=[[] for _ in range(n)]
for i in range(m):
    ai,bi=map(int, input().split())
    e[ai].append(bi)
    e_rev[bi].append(ai)

p_ord=[]
used=[0]*n
def dfs(v):
    used[v]=1
    for u in e[v]:
        if not used[u]:
            dfs(u)
    p_ord.append(v)
for i in range(n):
    if not used[i]:
        dfs(i)
compo = [0]*n
used=[0]*n
def dfs_rev(v,c):
    compo[v]=c
    used[v]=1
    for u in e_rev[v]:
        if not used[u]:
            dfs_rev(u,c)
cnt=0
for i in reversed(p_ord):
    if not used[i]:
        dfs_rev(i,cnt)
        cnt+=1
cc=[[] for _ in range(cnt+1)]
for i in range(n):
    cc[compo[i]].append(i)

print(len([cci for cci in cc if cci]))
for cci in cc:
    if cci:
        print(len(cci),*cci)
a = (input())

b = (input())

print(a*b)

print(2a+2b)


### FIXED CODE ###

a,b=map(int,input().split())
print(a*b,2*(a+b))
s = input()
count = 0

for i in range(len(s)):
    for j in range(len(s) - i):
        if int(s[i:i+j+1]) % 2019 == 0:
            count = count + 1

print(count)

### FIXED CODE ###

s, w = map(int, input().split())
if s > w:
  print("safe")
else:
  print("unsafe")
k = int(input())
a,b = list(map(int,input.split()))
res = 0
for i in range(a,b+1):
  if(i%k==0):
    res=1
    break
if(res==1):
  print("OK")
else:
  print("NG")

### FIXED CODE ###

k = int(input())
a,b = list(map(int,input().split()))
res = 0
for i in range(a,b+1):
  if(i%k==0):
    res=1
    break
if(res==1):
  print("OK")
else:
  print("NG")
import math
a,b,c,d = map(int, input().split())

count_c = int(b / c) - int((a-1) / c)
count_d = int(b / d) - int((a-1) / d)
lcm_cd = c * d / math.gcd(c, d)
count_cd = int(b / lcm_cd) - int((a-1) / lcm_cd)

print(b - a - int(count_c+count_d-count_cd) + 1)


### FIXED CODE ###

import fractions
a,b,c,d = map(int, input().split())

cnt_c = b // c - (a-1) // c
cnt_d = b // d - (a-1) // d
lcm = c * d // fractions.gcd(c, d)
cnt_cd = b // lcm - (a-1) // lcm

mul = cnt_c + cnt_d - cnt_cd

print(b - a + 1 - mul)
N, K = map(int, input().split())
A = list(map(int, input().split()))

if K >= N:
    lst = []
    n = 0
    for i in range(N):
        n = A[n]-1
        if A[n] in lst:
            n0 = lst.index(A[n])
            n1 = i
            break
        lst.append(A[n])

    num = n1 - n0
    K -= n0
    r = K % num
    n = n0
else:
    n = 0
    
for _ in range(r):
    n = A[n] - 1

print(n0+n+1)


### FIXED CODE ###

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

NN = [-1] * N
NN[0] = 0

i = 0
num = 0

while True:
    num += 1
    i = A[i] - 1
    if NN[i] != -1:
        n1 = NN[i]
        break
    NN[i] = num

n_ = num - n1

if K > n1:
    K -= n1
    t = NN.index(n1 + K % n_) + 1
    print(t)
else:
    t = NN.index(K) + 1
    print(t)
import numpy as np

x1,y1,x2,y2 = map(int,input().split())

a=np.array([x1,y1])
b=np.array([x2,y2])

T = np.array([[0,-1],[1,0]])

c = b + np.dot(T,b-a)
d = c + np.dot(T,c-b)
print(*c,*d)

### FIXED CODE ###

import numpy as np

x1,y1,x2,y2 = map(int,input().split())

a=np.array([x1,y1])
b=np.array([x2,y2])

T = np.array([[0,-1],[1,0]])

c = b + np.dot(T,b-a)
d = c + np.dot(T,c-b)
print(*c, end=' ')
print(*d)
a, b = map(int, input().split())


def f(keta, x):
    val = 2**keta
    if x < (2 ** (keta)):
        return False
    else:
        x -= (val-1)
        ans = x // (2*val) * val
        ans += min(val,x-val*2*(x//(2*val)))
        return ans

ans = []
i = 0
while f(i,b) != False:
    #print(i)
    val = f(i,b)
    if f(i,a-1) != False:
        val -= f(i,a-1)
    #print(val)
    ans += str(val % 2)
    i += 1
ans.reverse()
print(int(''.join(ans),2))

# print(ans)
# print(f(2, 4))
# print(f(1,4))
# print(bin(435))
# print(f(0,4),f(0,1))


### FIXED CODE ###

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


def f(keta, x):
    val = 2**keta
    if x < (2 ** (keta)):
        return False
    else:
        x -= (val-1)
        ans = x // (2*val) * val
        ans += min(val,x-val*2*(x//(2*val)))
        return ans
if b == 0:
    print(0)
    exit()
ans = []
i = 0
while f(i,b) != False:
    #print(i)
    val = f(i,b)
    if f(i,a-1) != False:
        val -= f(i,a-1)
    #print(val)
    ans += str(val % 2)
    i += 1

ans.reverse()
print(int(''.join(ans),2))

# print(ans)
# print(f(2, 4))
# print(f(1,4))
# print(bin(435))
# print(f(0,4),f(0,1))
n,k=map(int,input().split())
A = list(map(int,input().split()))
B = A*k
lA = len(A)
lB = len(B)
mod=10**9+7
cnt1=0
for i in range(lA):
    for j in range(i+1,lA):
        if A[i] > A[j]:
            cnt1+=1
cnt2=0
for i in range(lA):
    for j in range(lA):
        if A[i] > A[j]:
            cnt2+=1
print((cnt1*k+cnt2*(k*(k-1)//2))%mod)

### FIXED CODE ###

n,k=map(int,input().split())
A = list(map(int,input().split()))
lA = len(A)
mod=10**9+7
cnt1=0
for i in range(lA):
    for j in range(i+1,lA):
        if A[i] > A[j]:
            cnt1+=1
cnt2=0
for i in range(lA):
    for j in range(lA):
        if A[i] > A[j]:
            cnt2+=1
print((cnt1*k+cnt2*(k*(k-1)//2))%mod)
import math
A,B=map(int,input().split())

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

print(lcm(A,B))

### FIXED CODE ###

import fractions
A,B=map(int,input().split())

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

print(lcm(A,B))
# coding: utf-8
 
n, m, x, y = map(int, input().split())
xn = list(map(int, input().split()))
ym = list(map(int, input().split()))
flag = 0

if x < y:
    for i in range(x, y+1):
        if max(xn) < i and min(ym)>=i:
            print("No War")
            flag = 1
        if flag = 0 and i == y:
            print("War")
else:
    print("War")

### FIXED CODE ###

# coding: utf-8
 
n, m, x, y = map(int, input().split())
xn = list(map(int, input().split()))
ym = list(map(int, input().split()))
xn.append(x)
ym.append(y)
flag = 0

if max(xn) < min(ym):
    print("No War")
else:
    print("War")
s=input()
def roopR(l,n):
  if s[l]=='L':
    if n%2==0:
      return l
    else:
      return l-1
  else:
    return roopR(l+1,n+1)

def roopL(l,n):
  if s[l]=='R':
    if n%2==0:
      return l
    else:
      return l+1
  else:
    return roopL(l-1,n+1)

a=len(s)
endlist=[]
for j in range(a):
  endlist.append(0)
for k in range(a):
  if s[k]=='R':
    b=roopR(k,0)
    endlist[b] += 1
  else:
    b=roopL(k,0)
    endlist[b] += 1
print(*endlist)

### FIXED CODE ###

S=input()
dp=[0]*len(S)
a=0
for i in range(len(S)):
  if S[i]=='R':
    a+=1
  else:
    dp[i]+=a//2
    dp[i-1]+=a-a//2
    a=0
for i in range(len(S)-1,-1,-1):
  if S[i]=='L':
    a+=1
  else:
    dp[i]+=a//2
    dp[i+1]+=a-a//2
    a=0
print(*dp)
import itertools

L, R = map(int, input().split())
if R - L >= 2019:
    print(0)

comb = itertools.combinations(range(L, R + 1), 2)
result = float('inf')
for a, b in comb:
    mod = a * b % 2019
    if mod == 0:
        result = 0
        break
    elif mod < result:
        result = mod
print(result)

### FIXED CODE ###

L, R = map(int, input().split())
if R - L >= 2019:
    print(0)
else:
    result = float('inf')
    for i in range(L, R):
        for j in range(i + 1, R + 1):
            mod = (i * j) % 2019
            if mod == 0:
                result = 0
                break
            elif mod < result:
                result = mod
    print(result)
from collections import defaultdict, deque
import sys
import heapq
import bisect
import math
import itertools
import string
import queue
import copy
import time
import numpy as np
from fractions import gcd

sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7


def inp(): return int(sys.stdin.readline())


def inp_list(): return list(map(int, sys.stdin.readline().split()))


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


N = inp()
a = np.zeros((N, 3), dtype=int)

for i in range(N):
    a[i] = inp_list()

# dp[i + 1][j]: i日目までの活動で、i日目に活動 j (0: A, 1: B, 2:C) を選んだときの i + 1 日目の幸福の最大値
dp = np.zeros((N + 1, 3), dtype=int)
for i in range(N):
    for j in range(3): # i 日目の活動
        for k in range(3): # i + 1 日目の活動
            if j == k: continue
            dp[i + 1][k] = max(dp[i + 1][k], dp[i][j] + a[i][k])

ans = 0
for i in range(3):
    ans = max(ans, dp[N][i]) # N 日目を終了したときの幸福度 => dp[N][] (N + 1 番目)

# print(a)
# print(dp)
print(ans)


### FIXED CODE ###

from collections import defaultdict, deque
import sys
import heapq
import bisect
import math
import itertools
import string
import queue
import copy
import time
# import numpy as np
from fractions import gcd

sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7


def inp(): return int(sys.stdin.readline())


def inp_list(): return list(map(int, sys.stdin.readline().split()))


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


N = inp()
# a = np.zeros((N, 3), dtype=int)
a = [0] * N

for i in range(N):
    a[i] = inp_list()

# dp[i + 1][j]: i日目までの活動で、i日目に活動 j (0: A, 1: B, 2:C) を選んだときの i + 1 日目の幸福の最大値
# dp = np.zeros((N + 1, 3), dtype=int)
dp = [[0] * 3 for _ in range(N + 1)]
for i in range(N):
    for j in range(3): # i 日目の活動
        for k in range(3): # i + 1 日目の活動
            if j == k: continue
            dp[i + 1][k] = max(dp[i + 1][k], dp[i][j] + a[i][k])

ans = 0
for i in range(3):
    ans = max(ans, dp[N][i]) # N 日目を終了したときの幸福度 => dp[N][] (N + 1 番目)

# print(a)
# print(dp)
print(ans)
#"""
N, K = [int(n) for n in input().split(" ")]
Ps = [int(n) for n in input().split(" ")]
Cs = [int(n) for n in input().split(" ")]
#"""
"""
N = 10
K = 58345
Ps = [9, 1, 6, 7, 8, 4, 3, 2, 10, 5]
Cs = [695279662, 988782657, -119067776, 382975538, -151885171, -177220596, -169777795, 37619092, 389386780, 980092719]
"""
"""
N = 3
K = 3
Ps = [3, 1, 2]
Cs = [-1000,-2000,-3000]
"""

circles = []
already = {}
for p in range(N):
    if p not in already:
        tmp = []
        nowp = p
        while nowp not in tmp:
            tmp.append(nowp)
            already[nowp] = 1
            nowp = Ps[nowp] - 1
        circles.append(tmp)

#print(circles)

finalResult = -100000000000

def getCircleScore(circle, start, kk):
    #print(circle, start, kk)
    s = 0
    for k in range(kk):
        index = start + k
        if index >= len(circle):
            index = index % len(circle)
        s += Cs[circle[index]]
    return s

"""
maxCircle = []
maxCircleScore = -10000000000
maxIndex = 0
for circle in circles:
    CircleSum = sum([Cs[n] for n in circle])
    if maxCircleScore <= CircleSum:
        maxCircleScore = CircleSum
        maxCircle = circle
"""
#for circle in [maxCircle]:
for circle in circles:
    
    CircleSum = sum([Cs[n] for n in circle])
    #print(circle, CircleSum)
    score = 0
    if CircleSum > 0:
        score = K // len(circle) * CircleSum

    K = K % len(circle)
    if K == 0:
        K = len(circle)

    maxScore = -100000000000
    for start in range(len(circle)):
        #print("start", start)
        for kk in range(1, K+1):
            s = getCircleScore(circle, start, kk)
            #print(s)
            if maxScore <= s:
                maxScore = s

    final = score + maxScore

    if final >= finalResult:
        finalResult = final

print(finalResult)

### FIXED CODE ###

LL = input()


count = 0
maxcount = 0

for ll in LL:
    if ll == "R":
        count+= 1
    else:
        count = 0
    
    if maxcount <= count:
        maxcount = count

print(maxcount)
def dfs(v, p=-1):
    for u in to[v]:
        if u == p:
            continue
        ans[u] += ans[v]
        dfs(u, v)


N, Q = map(int, input().split())
to = [[] for _ in range(200005)]
ans = [0] * N
for _ in range(N-1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)
for _ in range(Q):
    p, x = map(int, input().split())
    p -= 1
    ans[p] += x
dfs(0)
print(*ans)

### FIXED CODE ###

import sys
input = sys.stdin.readline #for input speed
sys.setrecursionlimit(10**6) #for deep recursion
n, q = map(int, input().split())

tree_index = [[] for _ in range(n)]
for i in range(n-1):
  a,b = map(int, input().split())
  a -= 1
  b -= 1
  tree_index[a].append(b) # a<bとは限らないため、双方向にする
  tree_index[b].append(a)
ans = [0] * n
for i in range(q):
  p, x = map(int, input().split())
  ans[p-1] += x
def dfs(cur, par):
    for chl in tree_index[cur]:
      if chl == par: #parentとchildが等しい時はスキップ
        continue
      ans[chl] += ans[cur] 
      dfs(chl, cur)
dfs(0, -1)
print(*ans)
# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0057
"""
import sys


Area_memo = [0 for _ in range(10002)]         #  n??¬???????????????????????????????????° (0???????¨????)
Area_memo[0] = 1
def count_area(num):
    """
    ????????°??¨???????????°?????¢????????\????????????????????£????????????
    0 -> 1
    1 -> 2
    2 -> 4
    3 -> 7
    4 -> 11
    ?????£??????i??¬???????????????????????????????????°??????(i-1)??¬????????????????????° + ????????° ??¨?????????
    n?????°????????§??§10,000????????§????????¢???????????????????????????
    :param num:????????°
    :return: ???????????°
    """
    global Area_memo
    if Area_memo[num] == 0:
        Area_memo[num] = num + count_area(num-1)
    return Area_memo[num]


def main(args):
    for line in sys.stdin:
        num = int(line.strip())
        result = count_area(num)
        print(result)


if __name__ == '__main__':
    main(sys.argv[1:])

### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0057
"""
import sys


Area_memo = [0 for _ in range(10002)]         #  n??¬???????????????????????????????????° (0???????¨????)
Area_memo[0] = 1
def count_area(num):
    """
    ????????°??¨???????????°?????¢????????\????????????????????£????????????
    0 -> 1
    1 -> 2
    2 -> 4
    3 -> 7
    4 -> 11
    ?????£??????i??¬???????????????????????????????????°??????(i-1)??¬????????????????????° + ????????° ??¨?????????
    n?????°????????§??§10,000????????§????????¢???????????????????????????
    ??? ?????????????????¨???n?????§????????¨?????°????????????????????°????¢???????????????¨???????????????
    :param num:????????°
    :return: ???????????°
    """
    global Area_memo
    if Area_memo[num] == 0:
        Area_memo[num] = num + count_area(num-1)
    return Area_memo[num]


def count_area2(num):
    wa = num * (1 + num) // 2
    return wa + 1



def main(args):
    for line in sys.stdin:
        num = int(line.strip())
        result = count_area2(num)
        print(result)


if __name__ == '__main__':
    main(sys.argv[1:])
import sys

sys.setrecursionlimit(100000)

from math import log2


def build():
    dfs(tree, 0, -1, 0)
    pk0 = parent[0]
    for k in range(1, logn):
        pk1 = parent[k]
        for v in range(n):
            pkv = pk0[v]
            pk1[v] = -1 if pkv < 0 else pk0[pkv]
        pk0 = pk1


def dfs(tree, v, p, d):
    parent[0][v] = p
    depth[v] = d
    for child in tree[v]:
        if child != p:
            dfs(tree, child, v, d + 1)


def get(u, v):
    du, dv = depth[u], depth[v]
    if du > dv:
        u, v = v, u
        du, dv = dv, du
    for k in range(logn):
        if (dv - du) >> k & 1:
            v = parent[k][v]
    if u == v:
        return u
    for k in range(logn - 1, -1, -1):
        pk = parent[k]
        if pk[u] != pk[v]:
            u, v = pk[u], pk[v]
    return parent[0][u]


n = int(input())
tree = [set(map(int, input().split()[1:])) for _ in range(n)]

logn = int(log2(n)) + 1
parent = [[0] * n for _ in range(logn)]
depth = [0] * n
build()

q = int(input())
for _ in range(q):
    print(get(*map(int, input().split())))

### FIXED CODE ###

from math import log2


def build():
    dfs()
    pk0 = parent[0]
    for pk1 in parent[1:]:
        for v in range(n):
            pkv = pk0[v]
            pk1[v] = -1 if pkv < 0 else pk0[pkv]
        pk0 = pk1


def dfs():
    stack = [(0, -1, 0)]
    while stack:
        v, p, d = stack.pop()
        parent[0][v] = p
        depth[v] = d
        stack.extend((child, v, d + 1) for child in tree[v])


def get(u, v):
    du, dv = depth[u], depth[v]
    if du > dv:
        u, v = v, u
        du, dv = dv, du
    for k, pk in enumerate(parent):
        if (dv - du) >> k & 1:
            v = pk[v]
    if u == v:
        return u
    for pk in parent[logn - 1:None:-1]:
        pku, pkv = pk[u], pk[v]
        if pku != pkv:
            u, v = pku, pkv
    return parent[0][u]


n = int(input())
tree = [set(map(int, input().split()[1:])) for _ in range(n)]

logn = int(log2(n)) + 1
parent = [[0] * n for _ in range(logn)]
depth = [0] * n
build()

q = int(input())
for _ in range(q):
    print(get(*map(int, input().split())))
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
from itertools import accumulate #list(accumulate(A))
import math
 
N, K = mi()
A = li()
 
if K == 0:
    print(max(A))
    exit()
 
left = 0
right = max(A)
 
def count(num):
    cnt = 0
    for i in range(N):
        cnt += math.ceil(A[i] / num) - 1
    return cnt
 
while True:
    mid = (left + right) // 2
    if mid == 0:
        mid += 1
        break
    tmp = count(mid)
    if tmp == K:
        break
    elif tmp > K:
        if left == mid:
            mid = right
            break
        left = mid
    else:
        right = mid
 
if mid == 0 or mid == 1:
    print(mid)
    exit()
 
right = mid
 
while True:
    tmp = count(mid)
    if tmp == K and tmp != count(mid-1):
        print(mid)
        break
    elif tmp == K:
        right = mid
    else:
        if left == mid:
            print(right)
            break
        left = mid
    mid = (left + right) // 2
    if mid == 0:
        print(1)
        break

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**8)
def ii(): return int(sys.stdin.readline())
def mi(): return map(int, sys.stdin.readline().split())
def li(): return list(map(int, sys.stdin.readline().split()))
def li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]
#import bisect #bisect.bisect_left(B, a)
#from collections import defaultdict #d = defaultdict(int) d[key] += value
#from collections import Counter # a = Counter(A).most_common()
from itertools import accumulate #list(accumulate(A))
import math

N, K = mi()
A = li()

if K == 0:
    print(max(A))
    exit()

left = 0
right = max(A)

def count(num):
    cnt = 0
    for i in range(N):
        cnt += math.ceil(A[i] / num) - 1
    return cnt

while True:
    mid = (left + right) // 2
    if mid == 0:
        print(1)
        exit()
    tmp = count(mid)
    if right - left <= 1:
        mid = right
        break
    elif tmp > K:
        left = mid
    else:
        right = mid

right = mid

while True:
    tmp = count(mid)
    if right - left <= 1:
        print(right)
        break
    elif tmp == K:
        right = mid
    else:
        left = mid
    mid = (left + right) // 2
    if mid == 0:
        print(1)
        break