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

import copy

N, Q = map(int, input().split())
S = input()
ANSlist = [0]*Q
for i in range(Q):
    l ,r = map(int, input().split())
    SS = copy.deepcopy(S)
    SS = SS[l-1:r]
    for j in range(1,len(SS)):
        if SS[j] == "C" and SS[j-1] == "A":
            ANSlist[i] += 1
    
for i in range(len(ANSlist)):
    print(ANSlist[i])






### FIXED CODE ###

import copy

N, Q = map(int, input().split())
S = input()
t = [0]*(N+1)
for i in range(N):
    t[i+1] = t[i] + (1 if S[i:i+2] == "AC" else 0)

for i in range(Q):
    l, r = map(int, input().split())
    print(t[r-1]-t[l-1])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)

n, q = map(int,input().split())
g = [[] for _ in range(n+1)]
for  _ in range(n-1):
    a,b = map(int,input().split())
    g[a].append(b)
    g[b].append(a)
points = [0]*(n+1)
for _ in range(q):
    p, x = map(int,input().split())
    points[p] += x
# print(g)
# print(points)
def dfs(e,preve = -1):
    for nexte in g[e]:
        # print(nexte)
        if nexte == preve:
            continue
        points[nexte] = points[nexte] + points[e]
        dfs(nexte,e)
dfs(1)
print(*points[1:])



### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)

def input():
    return sys.stdin.readline()[:-1]

n, q = map(int,input().split())
g = [[] for _ in range(n+1)]
for  _ in range(n-1):
    a,b = map(int,input().split())
    g[a].append(b)
    g[b].append(a)
points = [0]*(n+1)
for _ in range(q):
    p, x = map(int,input().split())
    points[p] += x
# print(g)
# print(points)
def dfs(e,preve = -1):
    for nexte in g[e]:
        # print(nexte)
        if nexte == preve:
            continue
        points[nexte] = points[nexte] + points[e]
        dfs(nexte,e)
dfs(1)
print(*points[1:])
### BUGGY CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [-int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()
    DD = ((1,0),(0,1),(-1,0),(0,-1))

    N = NI()
    A = LI()

    y = [0] * (10**6 + 1)
    for i in A:
        y[i] += 1

    ans = 0
    for i in A:
        for j in range(1,int(math.sqrt(i)) + 1):
            if j == i and y[i] <= 1: continue
            if j == 1:
                if y[1]: break
                if y[i] > 1 : break
            else:
                if i % j == 0 and (y[j] or y[i//j]):
                    break
        else:
            ans += 1

    print(ans)
if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N = NI()

    y = [0] * (10**6 + 1)
    z = [0] * (10**6 + 1)
    A = []
    for x in sys.stdin.readline().split():
        x = int(x)
        A.append(x)
        y[x] += 1
        if y[x] == 1:
            c = x * 2
            while c <= 10**6:
                z[c] = 1
                c += x

    ans = 0
    for i in range(N):
        x = A[i]
        if y[x] > 1: continue

        if z[x] == 0:
            ans += 1

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

l, r = map(int, input().split())
rest = l*(l+1) % 2019
ans = rest

if r - l > 1:
  for i in range(l, r):
    for j in range(i+1, r+1):
      rest_next = i*j % 2019
      if rest_next < ans:
        ans = rest_next
print(ans)

### FIXED CODE ###

l, r = map(int, input().split())
rest = l*(l+1) % 2019
ans = rest
 
if r - l > 1:
  for i in range(l, r):
    if ans == 0:
      break
    for j in range(i+1, r+1):
      rest_next = i*j % 2019
      if rest_next < ans:
        ans = rest_next
      if ans == 0:
        break
print(ans)
### BUGGY CODE ###

n = input().split()
N = int(n[0])
Q = int(n[1])
S = input()

ans = []
for i in range(Q):
    lr = input().split()
    l = int(lr[0])
    r = int(lr[1])
    tmp = S[l-1:r]
    count = tmp.count('AC')
    ans.append(count)

for i in range(Q):
    print(str(ans[i]))




### FIXED CODE ###

from itertools import accumulate

N, Q = list(map(int, input().split()))
S = input()
A = [list(map(int, input().split())) for i in range(Q)]

tmp = []
for i in range(N-1):
    tmp_S  = S[i:i+2]
    if tmp_S == 'AC':
        tmp.append(1)
    else:
        tmp.append(0)

tmp2 = [0] + tmp
tmp2 = list(accumulate(tmp2))
#print(tmp2)

for j in A:
    print(tmp2[j[1]-1] - tmp2[j[0]-1])
### BUGGY CODE ###

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

count = 0
for i in range(N):
  count_ = 0
  judge = i+1
  for j in range(judge,N):
    if H[i] >= H[j]:
      count_ += 1
    else:
      break;
    H[i] = H[j]
  if count_ > count:
    count = count_
  if count == N-1:
    break;

print(count)

### FIXED CODE ###

N = int(input())
H = [int(e) for e in input().split()]
count_max = 0
i = 0
while i < N:
  judge = True
  count = 0
  tmp = i
  for j in range(tmp,N):
    if j < N-1:
      if H[j] >= H[j+1]:
        count += 1
      else:
        break;

  #print(count)
  if count_max < count:
    count_max = count
  if judge == True:
    i += count + 1

print(count_max)
### BUGGY CODE ###

q = list(map(int, input().split()))
w= list(map(int, input().split()))
memo=0
a=0
souwa=0
for i in range(q[0]-q[1]+1):
  k=0
  for j in range(q[1]):
    k+=w[i+j]
  if a<k:
    a=k
    memo=i
for p in range(q[1]):
  souwa+=(w[memo+p]+1)/2
print(souwa)

### FIXED CODE ###

n,k= list(map(int, input().split()))
j = list(map(int, input().split()))
s=0
sumlist=[0]*(n+1)
anslist=[0]*(n-k+1)
for i in range(n):
    s+=j[i]
    sumlist[i+1]=s
for i in range(len(anslist)):
     z=sumlist[i+k]-sumlist[i]
     anslist[i]=z
ans=max(anslist)
ans+=k
ans=ans/2
print(ans)
### BUGGY CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))
"""
high = float('inf')
low = -1

while low + 1 < high:
  mid = (low + high) // 2
  
  if min(sum(a), mid  :
    high = mid
  else:
    low = mid
print(high)
"""
for i in range(m):
  a[a.index(max(a))] = int(a[a.index(max(a))] / 2)
print(sum(a))

### FIXED CODE ###

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

import heapq
a = [-i for i in a]

heapq.heapify(a)
for i in range(m):
  b = heapq.heappop(a) * (-1)
  heapq.heappush(a, b // 2 * (-1))
print(-sum(a))
### BUGGY CODE ###

X=int(input())
#幅
from collections import deque
def dfs_2(start,goal):
  q = deque([])   # スタック
  q.append([start])
  flg = 0
  while flg==0:
    p = q.popleft()         # スタック取りだし（先頭）
    jp = len(p)
    if p[-1]-jp == goal or p[-1]+jp == goal:
      return jp
    else:
      p0 = [p[-1]]
      pp = [p[-1]+jp]
      pm = [p[-1]-jp]
      q.append(p+pp)# スタック追加
      q.append(p+pm)
      q.append(p+p0)

print(dfs_2(0,X))

### FIXED CODE ###

X=int(input())
s=0
for t in range(X+1):
  s+=t
  if s>=X:
    print(t)
    break
### BUGGY CODE ###

nq=list(map(int,input().split()))
n=[]
p=[]
t=[]
ans1=[]
ans2=[]
for i in range(nq[0]):
	inp=input().split()
	n.append(int(inp[1]))
	p.append(0)
	t.append(inp[0])

cnt=0
time=0
while n!=p:
	if n[0]==0:
		x=0
		y=0
		x=n[0]
		y=t[0]
		for j in range(len(n)-1):
			n[j]=n[j+1]
			t[j]=t[j+1]
		n[len(n)-1]=x
		t[len(t)-1]=y
	
	else:	
		n[0]=n[0]-nq[1]
		if n[0]<=0:
			time=time+(int(nq[1])*(cnt+1)+int(n[0]))
			cnt=0
			n[0]=0
			x=0
			y=0
			x=n[0]
			y=t[0]
			for j in range(len(n)-1):
				n[j]=n[j+1]
				t[j]=t[j+1]
			n[len(n)-1]=x
			t[len(t)-1]=y
			ans1.append(t[len(t)-1])
			ans2.append(time)
			
			
		else:
			x=0
			y=0
			x=n[0]
			y=t[0]
			for j in range(len(n)-1):
				n[j]=n[j+1]
				t[j]=t[j+1]
			n[len(n)-1]=x
			t[len(t)-1]=y
			cnt+=1
for i in range(nq[0]):
	print(ans1[i],ans2[i])
	
	
	
	


	


### FIXED CODE ###

n=[]
t=[]
nq=list(map(int,input().split()))
for i in range(nq[0]):
	inp=input().split()
	n.append(int(inp[1]))
	t.append(inp[0])
cnt1=0
while len(n)!=0:	
	n[0]=n[0]-nq[1]
	if n[0]<=0:
		cnt1=cnt1+nq[1]+n[0]
		print(t[0],cnt1)
		n.pop(0)
		t.pop(0)	
		
	else:
		n.append(n[0])
		t.append(t[0])
		n.pop(0)
		t.pop(0)
		cnt1+=nq[1]
### BUGGY CODE ###

s = str(input())
ans = 0
n = len(s)
A = [s[-1]]
count=0
i = n-1
while i>=0:
    if i == n-1:
        i-=1
    else:
        if A[count]==s[i]:
            A.append(s[i]+s[i-1])
            i -=2
            count+=1
        elif A[count]!=s[i] and i>1:
            A.append(s[i])
            count+=1
            i -= 1
        elif i==1 and s[i]==s[i-1]:
            A.append(s[i]+s[i-1])
            i-=2
        elif i==1 and s[i]!=s[i-1]:
            A.append(s[i])
            A.append(s[i-1])
            i-=2
print(len(A))

### FIXED CODE ###

s = str(input())
n = len(s)
ans = 1
count = 1
tmp = s[0]
while count < n:
    if s[count] == tmp:
        if count == n-1:
            ans -=1
        tmp = s[count:count+2]
        count +=2

    else:
        tmp = s[count]
        count +=1
    ans +=1

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

x,k,d=map(int,input().split())
x=abs(x)
sa=x//d
ans=x
pbk,mbk=0,0
bk1,bk2,bk3=1,1,1
if sa>=k:
  ans=x-d*k
else:
  ans=x-d*sa
  for i in range(k-sa):
    if abs(ans-d)!=abs(ans+d):
      ans=min(abs(ans-d),abs(ans+d))
      if ans==1:
        bk3=max(abs(ans-d),abs(ans+d))
      if bk3!=1:
        bk1=min(abs(ans-d),abs(ans+d))
        bk2=max(abs(ans-d),abs(ans+d))
        ans=1 if (k-sa-i)%2==1 else bk1
        break
    else:
      ans=0 if (k-sa-i)%2==0 else d
      break
    pbk=max(abs(ans-d),abs(ans+d))
    mbk=min(abs(ans-d),abs(ans+d))
print(ans)

### FIXED CODE ###

x,k,d=map(int,input().split())
x=abs(x)
sa=x//d
ans=x
pbk,mbk=0,0
bk1,bk2,bk3=1,1,1
mansbk,pansbk=0,0
if sa>=k:
  ans=x-d*k
else:
  ans=x-d*sa
  k=k-sa
  for i in range(k):
    mansbk=abs(ans-d)
    pansbk=abs(ans+d)
    if mansbk!=pansbk:
      ans=min(mansbk,pansbk)
      if bk3!=1:
        bk1=min(mansbk,pansbk)
        bk2=max(mansbk,pansbk)
        ans=mbk if (k-i)%2==0 else bk1
        break
      else:
        bk3=max(mansbk,pansbk) 
    else:
      ans=0 if (k-i)%2==0 else d
      break
    pbk=max(mansbk,pansbk)
    mbk=min(mansbk,pansbk)
print(ans)
### BUGGY CODE ###

N = int(input())
S = input()

R = []
G = []
B = []
for i in range(N):
    if S[i] == 'R':
        R.append(i+1)
    elif S[i] == 'G':
        G.append(i+1)
    elif S[i] == 'B':
        B.append(i+1)

ans = 0
for i in range(len(R)):
    for j in range(len(G)):
        ans += len(B)
        tmp_abs = abs(R[i]-G[j])

        if (min(R[i], G[j])-tmp_abs) in B:
            ans -= 1
        if (max(R[i], G[j])+tmp_abs) in B:
            ans -= 1
        if tmp_abs % 2 == 0 and (max(R[i], G[j])-(tmp_abs//2)) in B:
            ans -= 1

print(ans)


### FIXED CODE ###

import copy

N = int(input())
S = input()

RL = [0]*(N+1)
GL = copy.deepcopy(RL)
BL = copy.deepcopy(RL)
R = []
G = []
B = []
for i in range(N):
    if S[i] == 'R':
        R.append(i+1)
        RL[i+1] = 1
    elif S[i] == 'G':
        G.append(i+1)
        GL[i+1] = 1
    elif S[i] == 'B':
        B.append(i+1)
        BL[i+1] = 1

len_r = len(R)
len_g = len(G)
len_b = len(B)
ans = 0
if max(len_r, len_g, len_b) == len_b:
    for i in range(len_r):
        for j in range(len_g):
            ans += len_b
            tmp_abs = abs(R[i]-G[j])

            index = (min(R[i], G[j])-tmp_abs)
            if index > 0 and BL[index] == 1:
                ans -= 1

            index = (max(R[i], G[j])+tmp_abs)
            if index <= N and BL[index] == 1:
                ans -= 1

            if tmp_abs % 2 == 0 and BL[max(R[i], G[j])-(tmp_abs//2)] == 1:
                ans -= 1

elif max(len_r, len_g, len_b) == len_g:
    for i in range(len_r):
        for j in range(len_b):
            ans += len_g
            tmp_abs = abs(R[i]-B[j])

            index = (min(R[i], B[j])-tmp_abs)
            if index > 0 and GL[index] == 1:
                ans -= 1

            index = (max(R[i], B[j])+tmp_abs)
            if index <= N and GL[index] == 1:
                ans -= 1

            if tmp_abs % 2 == 0 and GL[max(R[i], B[j])-(tmp_abs//2)] == 1:
                ans -= 1

else:
    for i in range(len_g):
        for j in range(len_b):
            ans += len_r
            tmp_abs = abs(G[i]-B[j])

            index = (min(G[i], B[j])-tmp_abs)
            if index > 0 and RL[index] == 1:
                ans -= 1

            index = (max(G[i], B[j])+tmp_abs)
            if index <= N and RL[index] == 1:
                ans -= 1

            if tmp_abs % 2 == 0 and RL[max(G[i], B[j])-(tmp_abs//2)] == 1:
                ans -= 1
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    n, m = map(int, input().split())
    ls = [[int(_) for _ in input().split()] for _ in range(m)]
    
    lss = sorted(ls, key=lambda x: x[1])

    dp = [[] for _ in range(n)] 

    for i in range(m):
        dp[lss[i][0] - 1].append(lss[i][1])
    
    for k in range(m):
        th = dp[ls[k][0] - 1].index(ls[k][1]) + 1
        print(str(ls[k][0]).zfill(6) + str(th).zfill(6))

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    n, m = map(int, input().split())

    dp = [[] for _ in range(n)]
    ans = [0] * m

    for i in range(m):
        p, y = map(int, input().split())
        dp[p - 1].append((y, i))
    
    for j, k in enumerate(dp):
        k.sort()    
        for l, (s, t) in enumerate(k):
            ans[t] = str(j + 1).zfill(6) + str(l + 1).zfill(6)
    
    print(*ans, sep = "\n")


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

N, A = map(int, input().split())
# X = list(map(lambda x: int(x) - A, input().split()))
X = list(map(int, input().split()))
maxn = max(max(X), A)

dp = [[[0 for _ in range(maxn * N + 1)] for _ in range(N + 1)] for _ in range(N + 1)]
dp[0][0][0] = 1

for i in range(N):
    for j in range(i + 1):
        for k in range((i + 1) * maxn + 1):
            dp[i + 1][j][k] += dp[i][j][k]
            if k >= X[i]:
                dp[i + 1][j + 1][k] += dp[i][j][k - X[i]]

ans = 0
for j in range(1, N + 1):
    ans += dp[N][j][j * A]

print(ans)


### FIXED CODE ###

N, A = map(int, input().split())
X = list(map(lambda x: int(x) - A, input().split()))
maxn = max(max(X), A)

dp = [[0 for _ in range(2 * N * maxn + 1)] for _ in range(N + 1)]
dp[0][N * maxn] = 1

for i in range(N):
    for k in range(2 * N * maxn + 1):
        dp[i + 1][k] = dp[i][k]
        if 0 <= k - X[i] <= 2 * N * maxn:
            dp[i + 1][k] += dp[i][k - X[i]]

print(dp[N][N * maxn] - 1)
### BUGGY CODE ###

n = int(input())
aaa = list(map(int, input().split()))
mod = 1000000007
ans = 0
for i in range(n - 1):
    for j in range(i + 1, n):
        ans += aaa[i] * aaa[j] % mod
        ans %= mod
print(ans)

### FIXED CODE ###

n = int(input())
aaa = list(map(int, input().split()))
mod = 1000000007
c_sum = [0] * n
c_sum[n - 1] = aaa[n - 1]
ans = 0

for i in range(n - 2, 0, -1):
    c_sum[i] = (c_sum[i + 1] + aaa[i]) % mod

for i in range(n - 1):
    ans += aaa[i] * c_sum[i + 1] % mod
    ans %= mod

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

import collections
N=int(input())
AB=[list(map(int,input().split())) for i in range(N-1)]
AB_C=[0 for i in range(N-1)]
D=collections.Counter([i[0] for i in AB]+[i[1] for i in AB]).most_common()
M=D[0][1]
print(M)




data=[set() for i in range(N+1)]
idxdata=set([i for i in range(N-1)])
d=0
while idxdata:
    #print(idxdata)
    count_c=1
    delidx=set()
    for i in idxdata:
        a,b=AB[i]
        if a==D[d][0] or b==D[d][0]:
            while not(count_c not in data[a] and count_c not in data[b]):
                count_c+=1
            AB_C[i]=count_c
            data[a].add(count_c)
            data[b].add(count_c)
            delidx.add(i)
    d+=1
    idxdata=idxdata-delidx


for i in AB_C:
    print(i)


### FIXED CODE ###

from collections import deque
N=int(input())
AB=[list(map(int,input().split())) for i in range(N-1)]
P=[set() for i in range(N+1)]
C=[set() for i in range(N+1)]

for a,b in AB:
    P[a].add(b)
    P[b].add(a)
Cpath={}
stack=deque([1])
delset=set()
while stack:
    #print(C)
    #print(Cpath,"Cpath")
    a=stack[0]
    count=1
    for b in P[a]:
        #b=P[a][-1]
        while count in C[a]:
            count+=1
        C[a].add(count)
        C[b].add(count)
        Cpath[(a,b) if a<b else (b,a)]=count
        stack.append(b)
        #P[a].remove(b)
        P[b].remove(a)
    P[a].clear()
    stack.popleft()

print(max([Cpath[i] for i in Cpath]))
for a,b in AB:
    print(Cpath[(a,b)])
### BUGGY CODE ###

from itertools import product

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

delecious = []
for prod in product(a, b, c):
    delecious.append(sum(prod))

delecious.sort(reverse=True)

for i in range(k):
    print(delecious[i])

### FIXED CODE ###

import collections
import heapq
 
x, y, z, k = map(int, input().split())
ls = [list(map(int, input().split())) for _ in range(3)]
for i in range(3):
    ls[i].sort(reverse=True)
q = [(-sum([ls[i][0] for i in range(3)]), 0, 0, 0)]
res = []
used = collections.defaultdict(lambda: False)
while len(res) < k:
    s, i, j, l = heapq.heappop(q)
    res.append(-s)
    if i + 1 < x and not used[(i + 1, j, l)]:
        heapq.heappush(q, (-(ls[0][i + 1] + ls[1][j] + ls[2][l]), i + 1, j, l))
        used[(i + 1, j, l)] = True
    if j + 1 < y and not used[(i, j + 1, l)]:
        heapq.heappush(q, (-(ls[0][i] + ls[1][j + 1] + ls[2][l]), i, j + 1, l))
        used[(i, j + 1, l)] = True
    if l + 1 < z and not used[(i, j, l + 1)]:
        heapq.heappush(q, (-(ls[0][i] + ls[1][j] + ls[2][l + 1]), i, j, l + 1))
        used[(i, j, l + 1)] = True
print(*res, sep='\n')
### BUGGY CODE ###

N = int(input())
S = str(input())


R = 0
G = 0
B = 0

for i in range(N):
    s = S[i]
    if (s == 'R'):
        R +=1
    if (s == 'G'):
        G +=1
    if (s == 'B'):
        B +=1

count = R * G * B


for i in range(N):
    for j in range(1, N//2 + 1):
        if i + j*2 >= N:
            break
        if((S[i] != S[i + j]) & (S[i + j] != S[i + 2 * j]) & (S[i + 2 * j] != S[i])):
            count -= 1




print(count)

### FIXED CODE ###

n = int(input())
s = input()
 
r, b, g = 0, 0, 0
for i in range(n):
    if s[i] == 'R':
        r += 1
    if s[i] == 'G':
        g += 1
    if s[i] == 'B':
        b += 1
ans = r * g * b
 
for i in range(n):
    for j in range(1, n // 2 + 1):
        if i + 2 * j >= n:
            break
        if s[i] != s[i+j] and s[i] != s[i+2*j] and s[i+j] != s[i+2*j]:
            ans -= 1
 
print(ans)
### BUGGY CODE ###

def lcm(a):
  from fractions import gcd
  x = a[0]
  for i in range(1, len(a)):
    x = (x * a[i] // gcd(x, a[i]))
  return x

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

mod = 1000000000 + 7
min = lcm(a)
sum = 0
for i in range(n):
  sum = sum + (min//a[i]) 
  
print(sum%mod)



### FIXED CODE ###

from fractions import gcd
from functools import reduce
     
mod = 10 ** 9 + 7
     
def lcm_base(x, y):
    return (x * y) // gcd(x, y)
     
def lcm(numbers):
    return reduce(lcm_base, numbers, 1)
     
    # print('input >>')
N = int(input())
A = list(map(int,(input().split())))
     
lcmn = lcm(A)
    
ans = 0
for i in range(len(A)):
    ans += lcmn // A[i]
     
    # print('-----output-----')
print(int(ans%mod))
### BUGGY CODE ###

# [時間、変数、処理の種類]をイベントに追加。処理の種類は1：工事開始、2：工事終了、3：判定
from heapq import *

n, q = map(int, input().split())
events = []
ans = [-1] * q
koji = set()
for _ in range(n):
    s, t, x = map(int, input().split())
    events += [[s - x - 0.3, x, 1]]
    events += [[t - x - 0.7, x, 2]]
for i in range(q):
    d = int(input())
    events += [[d, i, 3]]
heapify(events)
for _ in range(n * 2 + q):
    j, h, s = heappop(events)
    if s == 1:
        koji.add(h)
    elif s == 2:
        koji.remove(h)
    else:
        if koji:
            ans[h] = min(koji)
print(*ans, sep="\n")


### FIXED CODE ###

import sys
from bisect import *

input = sys.stdin.readline

def f(n, q):
    xst = []
    for i in range(n):
        s, t, x = map(int, input().split())
        xst.append([x, s - x, t - x])
    xst.sort()

    ds = []
    for i in range(q):
        d = int(input())
        ds.append(d)

    ans = [-1] * q
    jump = [-1] * q

    for x, s, t in xst:
        i = bisect_left(ds, s)
        fi = bisect_left(ds, t)
        while i < fi:
            if jump[i] != -1:
                i = jump[i]
            else:
                ans[i] = x
                jump[i] = fi
                i += 1

    print(*ans, sep="\n")

n, q = map(int, input().split())
f(n, q)
### BUGGY CODE ###

from collections import deque

N, M = map(int, input().split())
job_list = {}
kouho = deque()
ans = 0
for _ in range(N):
  A, B = map(int, input().split())
  if A in job_list.keys():
    job_list[A].append(B)
  else:
    job_list[A] = deque([B])
    
for day in range(1, M + 1):
  try: 
    kouho += job_list[day]

  except KeyError:
    pass
  if len(kouho) != 0:
    temp = max(kouho)
    ans += temp
    kouho.remove(temp)

print(ans)
    
  

### FIXED CODE ###

import heapq

N, M = map(int, input().split())
AB_list = []
[heapq.heappush(AB_list, list(map(int, input().split()))) for _ in range(N)]
ans = 0
kouho = []

for day in range(1, M + 1):
    if len(AB_list) != 0:
        while AB_list[0][0] <= day:           
            heapq.heappush(kouho, heapq.heappop(AB_list)[1]*(-1))
            if len(AB_list) == 0:
                break
    if len(kouho) != 0:
        ans += heapq.heappop(kouho)

print(ans * (-1))
### BUGGY CODE ###

'''
AtCoder Grand Contest 030
A - Poisonous Cookies
'''


def main():
    a, b, c = map(int, input().split())
    oishii = b + c

    # クッキーを食べる
    while a + b > 0:

        c = c - 1 if c > 0 else 0

        if b > 0:
            b -= 1
        elif a > 0:
            a -= 1

    # まだcが残ってるなら一枚食べれる
    if c > 0:
        c -= 1

    print(oishii - (b + c))


if __name__ == "__main__":
    main()


### FIXED CODE ###

'''
AtCoder Grand Contest 030
A - Poisonous Cookies
'''


def main():
    a, b, c = map(int, input().split())

    '''
    A + B + 1 ≥ C ならすべての毒入りの
    クッキーを食べることができるので B + C。
    そうでないなら答えはB + (A + B + 1) 。
    ※「+1」は最後にCを食べるので
    '''
    print(b + min(c, a + b + 1))


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

L,R = map(int,input().split())
ans = 100000000
for i in range(L,R + 1):
    for j in range(i + 1,R + 1):
        if i*j % 2019 < ans:
            ans = i*j % 2019
print(ans)

### FIXED CODE ###

L,R = map(int,input().split())
ans = 100000000
for i in range(L,R + 1):
    if ans == 0:
        break
    for j in range(i + 1,R + 1):
        if i*j % 2019 < ans:
            ans = i*j % 2019
            if ans == 0:
                break
print(ans)
### BUGGY CODE ###

N = int(input())
S = []
for _ in range(N):
    S.append(input())

M = max([S.count(s) for s in set(S)])

R = [s for s in set(S) if S.count(s)==M]
R.sort()

for r in R:
    print(r)

### FIXED CODE ###

N = int(input())
S = []
for _ in range(N):
    S.append(input())

import collections    
C = collections.Counter(S)
M = C.most_common()[0][1]
R = [c for c in C.keys() if C[c]==M]
R.sort()

for r in R:
    print(r)
### BUGGY CODE ###

from heapq import heappush, heappop, heapify
import math
def solve():
	n , k= map(int, input().strip().split())
	a= [(-int(x),1,int(x)) for x in input().strip().split()]
	heapify(a)
	for i in range(k):
		x,cnt,orig = heappop(a)
		if -x < 1:
			return 1
		heappush(a,(-((orig+cnt)//(cnt+1)),cnt+1,orig))
	return -(heappop(a)[0])


print(solve())

### FIXED CODE ###

from heapq import heappush, heappop, heapify
import math
def check(a,mid,k):
	cnt = 0
	for x in a:
		cur_cnt = (x+mid-1)//mid - 1
		cnt+=cur_cnt
		if cnt > k:
			return False
	return True

def solve():
	n , k= map(int, input().strip().split())
	a= [int(x) for x in input().strip().split()]
	l = 0
	r = 10**9+20
	while r-l > 1:
		mid = (r+l)//2
		if check(a,mid,k):
			r = mid
		else:
			l = mid
	return l+1
 
print(solve())