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

import sys
from functools import lru_cache

sys.setrecursionlimit(10000000)

h, n = map(int, input().split())
m_list = []
max_a = 0
for i in range(n):
  a, b = map(int, input().split())
  m_list.append((a, b))
  if a > max_a:
    max_a = a
  
class Attack_Memo():
  def __init__(self):
    self.attack_memo = {}
  
  def attack(self, h):
    res_list = []
    if h <= 0:
      return 0
    if h in self.attack_memo:
      return self.attack_memo[h]
    for a, b in m_list:
      base_b = self.attack(h-a)
      res_list.append(base_b+b)
    self.attack_memo[h] = min(res_list)
    return min(res_list)

res = 100000000000
ins = Attack_Memo()
for i in range(h+a+1):
  tmp = ins.attack(i)
  if i >= h:
    if tmp <= res:
      res = tmp
print(res)

### FIXED CODE ###

import sys

sys.setrecursionlimit(10000000)

h, n = map(int, input().split())
m_list = []
max_a = 0
for i in range(n):
  a, b = map(int, input().split())
  m_list.append((a, b))
  if a > max_a:
    max_a = a
  
class Attack_Memo():
  def __init__(self):
    self.attack_memo = {}
  
  def attack(self, h):
    res_list = []
    if h <= 0:
      return 0
    if h in self.attack_memo:
      return self.attack_memo[h]
    for a, b in m_list:
      base_b = self.attack(h-a)
      res_list.append(base_b+b)
    self.attack_memo[h] = min(res_list)
    return min(res_list)

res = 100000000000
ins = Attack_Memo()
for i in range(h+a+1):
  tmp = ins.attack(i)
  if i >= h and tmp <= res:
    res = tmp
print(res)
### BUGGY CODE ###

# E - Colorful Blocks

MOD = 998244353
N, M, K = map(int, input().split())

def comb_mod(n, r, p):
    num = 1
    den = 1
    r = min(r, n-r)
    for i in range(r):
        num = (num * (n-i)) % p
        den = (den * (i+1)) % p
    return num * pow(den, p-2, p)

ans = 0
for i in range(K+1):
    ans = (ans + (M*pow(M-1, N-1-i,MOD)) * comb_mod(N-1, i, MOD))%MOD

print(ans)


### FIXED CODE ###

# E - Colorful Blocks

MOD = 998244353
N, M, K = map(int, input().split())

# 予め階乗を計算しておく
f = [1]
for i in range(N):
    f.append(f[i]*(i+1)%MOD)

# 組み合わせ関数
def comb_mod(n, r, p):
    return f[n] * pow(f[r], p-2, p) * pow(f[n-r], p-2, p)

ans = 0
for i in range(K+1):
    ans = (ans + (M*pow(M-1, N-1-i,MOD)) * comb_mod(N-1, i, MOD))%MOD

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

n,m=map(int,input().split())
h=list(map(int,input().split()))
c=[list(map(int,input().split()))for i in [0]*m]
k=0
for i in range(1,n+1):
    l=1
    for j in c:
        if i in j:
            a=j.index(i)
            if h[i-1]<=h[j[-a-1]-1]:
                l=0
                break
    k+=l
print(k)

### FIXED CODE ###

n,m=map(int,input().split())
h=list(map(int,input().split()))
k=[]
for i in [0]*m:
    a,b=map(int,input().split())
    a-=1
    b-=1
    if h[a]==h[b]:
        k+=[a]+[b]
    if h[a]>h[b]:
        k+=[b]
    if h[a]<h[b]:
        k+=[a]
print(n-len(set(k)))
### BUGGY CODE ###

import sys
sys.setrecursionlimit(100000)
def intinput():return map(int,input().split())

factmemo={0:1} #階乗
def fact(n):
    if n in factmemo:
        return factmemo[n]
    k = n*fact(n-1)
    factmemo[n]=k
    return k

def comb(a,b): return fact(a)//(fact(a-b)*fact(b)) #組み合わせ

for i in range(10):
    fact(i+10000)
n=int(input())
s={}
for i in range(n):
    t=list(input())
    t.sort()
    t="".join(t)
    try:
        s[t]+=1
    except:
        s[t]=1
ans=0
for i in s.values():
    if i!=1:
        ans+=comb(i,2)
print(ans)

### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)
def intinput():return map(int,input().split())

n=int(input())
s={}
for i in range(n):
    t=list(input())
    t.sort()
    t="".join(t)
    try:
        s[t]+=1
    except:
        s[t]=1
ans=0
for i in s.values():
    if i!=1:
        ans+=i*(i-1)//2
print(ans)
### BUGGY CODE ###

import copy
import math
import sys

sys.setrecursionlimit(10 ** 7)

N = int(input())
s_list = [input() for i in range(N)]


def split(word):
    return [char for char in word]


normalized_s_list = [''.join(sorted(split(s))) for s in s_list]

uniqued_s_list = set(normalized_s_list)

duplicated_s_list = copy.deepcopy(normalized_s_list)
for s in uniqued_s_list:
    duplicated_s_list.remove(s)

duplicated_s_list = list(set(duplicated_s_list))

result = 0
for s in duplicated_s_list:
    count = normalized_s_list.count(s)
    result += (1 / 2) * count * (count - 1)

print(int(result))


### FIXED CODE ###

import copy
import math
import sys

sys.setrecursionlimit(10 ** 7)

N = int(input())
s_list = [input() for i in range(N)]


def split(word):
    return [char for char in word]


normalized_s_list = sorted([''.join(sorted(split(s))) for s in s_list])

uniqued_s_list = sorted(list(set(normalized_s_list)))

j = 0
counter = 0
result = 0
for s in normalized_s_list:
    if s == uniqued_s_list[j]:
        counter += 1
    else:
        result += (1 / 2) * counter * (counter - 1)
        j += 1
        counter = 1  # このとき s と uniqued_s_list[j] は同じはずなので

result += (1 / 2) * counter * (counter - 1)
print(int(result))
### BUGGY CODE ###

a, b = map(int, input().split())
s = input()
l = [0] * a

for x in range(a - 1):
    if s[x:x+2] == "AC":
        l[x] = 1

for x in range(b):
    i, j = map(int, input().split())
    print(sum(l[i-1:j-1]))

### FIXED CODE ###

a, b = map(int, input().split())
s = input()
l = [0] * a
c = 0

for x in range(a - 1):
    if s[x:x+2] == "AC":
        c += 1
    l[x] = c

for x in range(b):
    i, j = map(int, input().split())
    print(l[j-2] - l[i-2])
### BUGGY CODE ###

from sys import stdin

n,q=map(int,input().split())
s=list(input())
l = [stdin.readline().rstrip().split() for _ in range(q)]

for i,j in l:
    ans=0
    for k in range(int(i)-1,int(j)-1):
        if s[k]=="A" and s[k+1]=="C":
            ans+=1
    print(ans)

### FIXED CODE ###

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 ###

n,q=map(int,input().split())
s=input()
m=len(s)-1
idx=[0 for i in range(m)]

for i in range(m):
    if s[i]=="A" and s[i+1]=="C":idx[i]=1
ans=[]
for i in range(q):
    l,r=map(int,input().split())
    ans.append(sum(idx[l-1:r-1]))

for i in ans:
    print(i)

### FIXED CODE ###

n,q=map(int,input().split())
s=input()
idx=[0 for i in range(n+1)]

for i in range(n-1):
    if s[i:i+2]=="AC":idx[i+1]=idx[i]+1
    else:idx[i+1]=idx[i]

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

import math
n = int(input())
 
ans = [0]*(n+1)
for i in range(1,n+1):
	for x in range(1,100):
		for y in range(1,100):
			if pow(x+y,2) - 4*(pow(x,2) + x*y +pow(y,2) - i) >= 0:
				p = (1/2)*(-(x+y) + math.sqrt(pow(x+y,2) - 4*(pow(x,2) +x*y +pow(y,2) - i)))
				q = (1/2)*(-(x+y) - math.sqrt(pow(x+y,2) - 4*(pow(x,2) +x*y +pow(y,2) - i)))
				if (p%1 == 0 and p >= 1) or (q%1 == 0 and q >= 1):
					ans[i] += 1
for i in range(1,n+1):
	print(ans[i])

### FIXED CODE ###

n = int(input())

ans = [0]*(n+1)

for x in range(1,100):
	for y in range(1,100):
		for z in range(1,100):
			if pow(x,2) + pow(y,2) + pow(z,2) + x*y + y*z + z*x <= n:
				ans[pow(x,2) + pow(y,2) + pow(z,2) + x*y + y*z + z*x] += 1			
for i in range(1,n+1):
	print(ans[i])
### BUGGY CODE ###

# Problem E - Divisible Substring

from collections import Counter

# 組み合わせ
def combinations_count(n, r):
    return n * (n - 1) // r

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

# count
if P==2 or P==5:
    ans = 0
    for i in range(N-1, -1, -1):
        s = int(S[i])
        if s%P==0:
            ans += i + 1
    # output
    print(ans)
else:
    p_nums = [0]*(N+1)
    s = ""
    for i in range(N-1, -1, -1):
        s = S[i] + s
        p_nums[N - i] = int(s)%P
    p_counter = Counter(p_nums)
    ans = 0
    for key in p_counter.keys():
        p_c = p_counter[key]
        if p_c>=2:
            ans += combinations_count(p_c, 2)
    print(ans)


### FIXED CODE ###

# Problem E - Divisible Substring

from collections import Counter

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

# count
if P==2 or P==5:
    ans = 0
    for i in range(N-1, -1, -1):
        s = int(S[i])
        if s%P==0:
            ans += i + 1
    # output
    print(ans)
else:
    p_nums = [0]*(N+1)
    s = 0
    for i in range(N-1, -1, -1):
        s = int(S[i]) * pow(10, N - i - 1, P) + s
        p_nums[N - i] = s%P
    p_counter = [0]*P
    for i in range(N+1):
        p_counter[p_nums[i]] += 1
    ans = 0
    for i in range(P):
        ans += p_counter[i] * (p_counter[i] - 1) // 2
    print(ans)
### BUGGY CODE ###

import sys
for n in sys.stdin:
  num = int(n)
  ifprime = [1]*(num+1)
  ifprime[0] = ifprime[1] = 0
  a = 2
  while a*a <= num:
    if ifprime[a]:
      b = a*a
      while b <= num:
        ifprime[b] = 0
        b += a
    a += 1
  print sum(ifprime)

### FIXED CODE ###

import sys
ifprime = [1]*(1000000)
ifprime[0] = ifprime[1] = 0
a = 2
while a < 1000000:
  if ifprime[a]:
    b = a*a
    while b < 1000000:
      ifprime[b] = 0
      b += a
  a += 1
for n in sys.stdin:
  print sum(ifprime[:int(n)+1])
### BUGGY CODE ###

N,M,Q=map(int,input().split())
import numpy as np
trains=np.zeros((N+1,N+1),dtype=int)
for i in range(M):
  l,r=map(int,input().split())
  trains[l][r]+=1
  
trains=np.cumsum(trains,axis=0)
trains=np.cumsum(trains,axis=1)

for i in range(Q):
  p,q=map(int,input().split())
  print(trains[q,q]-trains[p-1,q]-trains[q,p-1]+trains[p-1,p-1])


### FIXED CODE ###

N,M,Q=map(int,input().split())
pos=[[0 for i in range(N+1)] for j in range(N+1)]

for i in range(M):
  l,r=map(int,input().split())
  pos[l][r]+=1

for l in range(N+1):
  sums=0
  for r in range(N):
    pos[l][r+1]=pos[l][r]+pos[l][r+1]
    
for r in range(N+1):
  sums=0
  for l in range(N):
    pos[l+1][r]=pos[l][r]+pos[l+1][r]

for i in range(Q):
  p,q=map(int,input().split())
  print(pos[q][q]-pos[p-1][q]-pos[q][p-1]+pos[p-1][p-1])
### BUGGY CODE ###

n = int(input())
s = input()

r = s.count('R')
g = s.count('G')
b = s.count('B')

# 1つ目の条件を満たす
first_conditions = r*g*b
# 一つ目の条件は満たすが、2つ目の条件は満たさない
second_condition = 0
sum_ = 0
for i in range(n):
    for j in range(i,n):
        for k in range(j,n):
                if j-i == k-j and (s[i] != s[j] and s[j] != s[k] and s[i] != s[k]):
                    second_condition += 1
print(first_conditions-second_condition)

### FIXED CODE ###

n = int(input())
s = input()
r_ary = []
g_ary = []
b_ary = []
for i in (s):
    if i == 'R':
        r_ary.append(i)
    elif i == 'G':
        g_ary.append(i)
    elif i == 'B':
        b_ary.append(i)
r = len(r_ary)
g = len(g_ary)
b = len(b_ary)
first_conditions = r*g*b
for i in range(n-2):
    for j in range(i+1,n-1):
        if 2*j-i<n and s[i]!=s[2*j-i] and s[j]!=s[2*j-i] and s[i]!=s[j]:
            first_conditions -= 1
print(first_conditions)
### BUGGY CODE ###

b,r,g,n=map(int,input().split())
ans=0
for i in range(3000//r+1):
    for j in range(3000//g+1):
        if n-j*g-i*r>=0 and (n-j*g-i*r)%b==0:
            ans+=1
print(ans)


### FIXED CODE ###

b,r,g,n=map(int,input().split())
ans=0
for i in range(3000//r+1):
    for j in range(3000//g+1):
        if n-j*g-i*r>=0 and (n-j*g-i*r)%b==0:
            ans+=1
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, M: int, K: int, A: "List[int]", B: "List[int]"):
    a = 0
    a_n = [a]
    for a_i in A:
        a += a_i
        a_n.append(a)

    b = 0
    b_n = [b]
    for b_i in B:
        b += b_i
        b_n.append(b)

    maxs = []
    max_j = M
    for i, a in enumerate(a_n):
        for j, b in enumerate(b_n[:max_j+1][::-1]):
            #print("j, b", j, b)
            if b <= (K-a):
                #print("a, b:", a, b)
                #print("i, j", i, j)
                maxs.append(i+max_j-j)
                max_j -= j
                #print("maxs:", maxs)
                break

    return max(maxs)


# Generated by 1.1.7.1 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
    M = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    B = [int(next(tokens)) for _ in range(M)]  # type: "List[int]"
    print(solve(N, M, K, A, B))

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, M: int, K: int, A: "List[int]", B: "List[int]"):
    a = 0
    a_n = [a]
    for a_i in A:
        a += a_i
        a_n.append(a)

    b = 0
    b_n = [b]
    for b_i in B:
        b += b_i
        b_n.append(b)

    ans = 0
    j = M
    for i, a in enumerate(a_n):
        if a > K:
            break
        while b_n[j] > (K-a):
            j -= 1
        ans = max(ans, i+j)

    return ans


# Generated by 1.1.7.1 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
    M = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    B = [int(next(tokens)) for _ in range(M)]  # type: "List[int]"
    print(solve(N, M, K, A, B))

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

n = int(input())
A = list(map(int, input().split()))
r = 0
for i in range(n):
    p, x = 0, 0
    for j in range(i, n):
        p += A[j]
        x ^= A[j]
        if p == x:
            r += 1
        else:
            break
print(r)

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
ans = 0
s = 0
j = 0
for i in range(n):
    while j < n and not (s & A[j]):
        s ^= A[j]
        j += 1
    ans += j-i
    s ^= A[i]
print(ans)
### BUGGY CODE ###

A, B, C, K = map(int, input().split())

def judge(n):
    if abs(n) > 10**18:
        print('Unfair')
    else:
        print(n)

if K == 0:
    judge(A-B)
else:
    sum = A + B + C
    for i in range(1, K+1):
        sum *= K
        A = sum - A
        B = sum - B
    judge(A-B)

### FIXED CODE ###

A, B, C, K = map(int, input().split())

def judge(n):
    if abs(n) > 10**18:
        print('Unfair')
    else:
        print(n)

if K % 2 == 0:
    judge(A-B)
else:
     judge(B-A)
### BUGGY CODE ###

from collections import defaultdict
d = defaultdict(int)
S=input()
S=S[::-1]
_=''
MOD=2019
for s in S:
  _=s+_
  d[int(_)%MOD]+=1
ans=0
for k in d.values():
  ans=ans+k*(k-1)//2
print(ans+d[0])

### FIXED CODE ###

from collections import defaultdict
d = defaultdict(int)
S=input()
S=S[::-1]
i=1
x=0
MOD=2019
for s in S:
  x+=(int(s)*i)%MOD
  x%=MOD
  d[x]+=1
  i*=10
  i%=MOD
ans=0
for k in d.values():
  ans=ans+k*(k-1)//2
print(ans+d[0])
### BUGGY CODE ###

N,A=map(int,input().split())
X=[int(a) for a in input().split()]
X.insert(0,0)

#[x]までのy個を使ってzを作る場合の数を数え上げるdp
#dp[x][y][z]=dp[x-1][y][z]+dp[x-1][y-1][z-X[x]](zが残っている場合）
#dp[x][y][z]=dp[x-1][y][z](zが残っていない場合)
dp=[[[0 for i in range(N*50+1)] for j in range(N+1)] for k in range(N+1)]
for i in range(N+1):
  dp[i][0][0]=1
for i in range(1,N+1):
  for j in range(1,N+1):
    for k in range(N*50+1):
      if k < X[i]:
        dp[i][j][k]=dp[i-1][j][k]
      else:
        dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-1][k-X[i]]

#ansはN枚中j枚使用かつj枚*平均Aを作れる個数。
ans=0
for x in range(1,N+1):
  ans+=dp[N][x][x*A]
print(ans)

### FIXED CODE ###

def solve(N,A,X):  
  X.append(0)
  X.sort()
  ma=sum(X)

#[x]までのy個を使ってzを作る場合の数を数え上げるdp
#dp[x][y][z]=dp[x-1][y][z]+dp[x-1][y-1][z-X[x]](zが残っている場合）
#dp[x][y][z]=dp[x-1][y][z](zが残っていない場合)
  dp=[[[0] * (ma+1) for _ in range(N+1)] for _ in range(N+1)]
  
#[x]までの0個を使って0を作る方法は1つ（dp初期化）
  for i in range(N+1):
    dp[i][0][0]=1
  for i in range(1,N+1):
    cnt=X[i]
    for j in range(1,N+1):
      for k in range(ma+1):
        if k < cnt:
          dp[i][j][k]=dp[i-1][j][k]
        else:
          dp[i][j][k]=dp[i-1][j][k]+dp[i-1][j-1][k-cnt]

#ansはN枚中j枚使用かつj枚*平均Aを作れる個数。
  ans=0
  for x in range(1,N+1):
    if x*A<=ma:
      ans+=dp[N][x][x*A]
  return ans

N,A=map(int,input().split())
X=[int(a) for a in input().split()]
ans=solve(N,A,X)
print(ans)
### BUGGY CODE ###

import math
n = int(input())
a = list(map(int,input().split()))
s = [0]*(10**6+1)
t = [0]*169
u = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,
     101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199,
     211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293,
     307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397,
     401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499,
     503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599,
     601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691,
     701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797,
     809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887,
     907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009]
v = 0
m = 169
for i in range(n):
    for j in range(m):
        if(a[i]%u[j] == 0):
            t[j] += 1
            while(a[i]%u[j] == 0):
                a[i] //= u[j]
            if(a[i] == 1):
                break
    if(a[i] != 1):
        s[a[i]] += 1
        v += 1
if(max(t) == n):
    print('not coprime')
elif(max(t) <= 1):
    z = 0
    if(v > 0):
        if(max(s) <= 1):
            print('pairwise coprime')
        else:
            print('setwise coprime')    
    else:
        print('pairwise coprime')
else:
    print('setwise coprime')

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
r = max(a)+1
s = []
t = [0]*r
for i in range(r):
    s.append([])
for i in range(2,r):
    if(s[i] == []):
        for j in range(1,-(-r//i)):
            s[i*j].append(i)
for i in range(n):
    for j in range(len(s[a[i]])):
        t[s[a[i]][j]] += 1
if(max(t) == n):
    print('not coprime')
elif(max(t) <= 1):
    print('pairwise coprime')
else:
    print('setwise coprime')
### BUGGY CODE ###

N=int(input())
mod=998244353
Combi=[1]
for i in range(1,N+1):
    Combi.append(Combi[-1]*(N-i+1)*pow(i,mod-2,mod)%mod)
SC=0
for i in range(N//2+1,N+1):
    SC=(SC+Combi[i]*pow(2,N-i,mod))%mod
print((pow(3,N,mod)-SC*2)%mod)


### FIXED CODE ###

N=int(input())
mod=998244353

FACT=[1]
for i in range(1,N+1):
    FACT.append(FACT[-1]*i%mod)

FACT_INV=[pow(FACT[-1],mod-2,mod)]
for i in range(N,0,-1):
    FACT_INV.append(FACT_INV[-1]*i%mod)

FACT_INV.reverse()

POW=[1]
for i in range(N):
    POW.append(POW[-1]*2%mod)

def Combi(a,b):
    return FACT[a]*FACT_INV[b]*FACT_INV[a-b]%mod

SC=0
for i in range(N//2+1,N+1):
    SC+=Combi(N,i)*POW[N-i]

print((pow(3,N,mod)-SC*2)%mod)
### BUGGY CODE ###

n, k = map(int, input().split())
p = list(map(int,input().split()))
s = [0] * n

for i in range(n-k+1):
    s[i] = sum(p[i:i+k])

print((k+max(s))/2)

### FIXED CODE ###

n, k = map(int, input().split())
p = list(map(int,input().split()))
s = [0] * (n-k+1)
s_0 = sum(p[0:k])
s[0] = s_0
for i in range(n-k):
    s[i+1] = s[i] + p[k+i] - p[i]

print((k+max(s))/2)
### BUGGY CODE ###

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

for i in range(M):
    max_item_index = A.index(max(A))
    A[max_item_index] = int(A[max_item_index] / 2)

print(sum(A))

### FIXED CODE ###

def pushHeap(array, elem):
    n = len(array)
    array.append(elem)
    while n != 0:
        i = int((n - 1) / 2)
        if array[n] > array[i]:
            tmp = array[n]
            array[n] = array[i]
            array[i] = tmp
        n = i


def popHeap(array):
    n = len(array) - 1
    array[0] = array[n]
    del array[-1]
    i = 0
    while 2 * i + 1 < n:
        j = 2 * i + 1
        if j != n - 1 and array[j] < array[j + 1]:
            j += 1
        if array[i] < array[j]:
            tmp = array[j]
            array[j] = array[i]
            array[i] = tmp
        i = j


N, M = map(int, input().split())
A = list(map(int, input().split()))
heap_A = []

for a in A:
    pushHeap(heap_A, a)

for _ in range(M):
    discount_max = int(heap_A[0] / 2)
    popHeap(heap_A)
    pushHeap(heap_A, discount_max)

print(sum(heap_A))
### BUGGY CODE ###

N, S = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
MOD =   998244353
DP = [[0 for p in range(S+1)]for x in range(N)]
ans = N * (A[0]==S)
if A[0]<=S:
    DP[0][A[0]] = 1
for n,a in enumerate(A):
    if n!=0:
        #もらう
        for p in range(S+1):
            DP[n][p] = DP[n-1][p]
        for p in range(a,S+1):
            DP[n][p] = DP[n-1][p] + DP[n-1][p-a]
        #初期化
        if a<=S:DP[n][a] += n+1
    ans += (DP[n][S]*(N-n))% MOD
    DP[n][S] = 0
    ans %= MOD
print(ans)

### FIXED CODE ###

N, S = [int(i) for i in input().split()]
A = [int(i) for i in input().split()]
MOD =   998244353
DP = [[0 for p in range(S+1)]for x in range(N)]
ans = N * (A[0]==S)
if A[0]<=S:
    DP[0][A[0]] = 1
for n,a in enumerate(A):
    if n!=0:
        #もらう
        for p in range(a,S+1):
            DP[n][p] += DP[n-1][p-a]
        for p in range(S+1):
            DP[n][p] += DP[n-1][p]
            DP[n][p] %= MOD
        #初期化
        if a<=S:DP[n][a] += n+1
    ans += (DP[n][S]*(N-n))% MOD
    DP[n][S] = 0
    ans %= MOD
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

from collections import Counter
import bisect
import numpy as np

l = Counter(A).most_common()
l = [b for a, b in l]
M = len(l)
l = np.sort(l)
m = np.cumsum(l)
p = m[-1]

maximum_operation = [0] * N

ll = []
for x in reversed(range(1, N+1)):
    a = bisect.bisect_left(l, x)
    if a == 0:
        b = M*x
        c = 0
    elif a >= M:
        b = 0
        c = p
    else:
        b = (M-a)*x
        c = m[a-1] 
    ll.append((b + c)/x)

for K in range(M):
    maximum_operation[K] = N - bisect.bisect_left(ll, K+1)

for m in maximum_operation:
    print(m)

### FIXED CODE ###

import sys
input = sys.stdin.readline

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

#output
from collections import Counter
import bisect

l = Counter(A).most_common()
l = [b for a, b in l]
M = len(l)
l.sort()
p = sum(l)

maximum_operation = [0] * N

ll = []
for x in reversed(range(1, N+1)):
    a = bisect.bisect_left(l, x)
    if a == 0:
        b = M*x
        c = 0
    elif a >= M:
        b = 0
        c = p
    else:
        b = (M-a)*x
        c = sum(l[0:a]) 
    ll.append((b + c)/x)

for K in range(M):
    maximum_operation[K] = N - bisect.bisect_left(ll, K+1)

for m in maximum_operation:
    print(m)