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

N = int(input())
A = list(map(int, input().split()))
S = sum(A)/2
x1 = S - sum([A[i] for i in range(1, N, 2)])
ans = "%d"%(x1*2)
x = x1
for i in range(N-1):
  x = A[i]-x
  ans += " %d"%(x*2)
print(ans)


### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
S = sum(A)/2
x1 = S - sum([a for a in A[1:N:2]])
ans = "%d"%(x1*2)
x = x1
for a in A[:-1]:
  x = a-x
  ans += " %d"%(x*2)
print(ans)
### BUGGY CODE ###

#!/usr/bin/env python3

import sys

def main():
    sys.setrecursionlimit(10 ** 6)
    n = int(input())
    ranks = [0 for i in range(n)]
    adjs = [[] for i in range(n)]
    edges = []
    for i in range(n - 1):
        a, b = map(int, input().split())
        edges.append((a - 1, b - 1))
        ranks[a - 1] += 1
        ranks[b - 1] += 1
        adjs[a - 1].append(b - 1)
        adjs[b - 1].append(a - 1)

    visited = [False for i in range(n)]
    color_used = [set() for i in range(n)]
    colors = {}  # (mi, ma) |-> color
    dfs(0, adjs, visited, color_used, colors)

    print(max(ranks))
    for i in range(n - 1):
        a, b = edges[i]
        mi = min(a, b)
        ma = max(a, b)
        print(colors[(mi, ma)])

def dfs(i, adjs, visited, color_used, colors):
    visited[i] = True
    for j in adjs[i]:
        if visited[j]:
            continue
        for c in range(1, 100005):
            if c in color_used[i]:
                continue
            # if c in color_used[j]:
            #     continue
            color_used[i].add(c)
            color_used[j].add(c)
            mi = min(i, j)
            ma = max(i, j)
            colors[(mi, ma)] = c
            break
        dfs(j, adjs, visited, color_used, colors)

if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3

import sys
import random

def main():
    sys.setrecursionlimit(10 ** 6)
    n = int(input())
    ranks = [0 for i in range(n)]
    adjs = [[] for i in range(n)]
    edges = []
    for i in range(n - 1):
        a, b = map(int, input().split())
        edges.append((a - 1, b - 1))
        ranks[a - 1] += 1
        ranks[b - 1] += 1
        adjs[a - 1].append(b - 1)
        adjs[b - 1].append(a - 1)

    for i in range(n):
        random.shuffle(adjs[i])
    visited = [False for i in range(n)]
    colors = {}  # (mi, ma) |-> color
    dfs(0, adjs, visited, -1, colors)

    print(max(ranks))
    for i in range(n - 1):
        a, b = edges[i]
        mi = min(a, b)
        ma = max(a, b)
        print(colors[(mi, ma)])

def dfs(i, adjs, visited, color_used, colors):
    visited[i] = True
    c = 1
    for j in adjs[i]:
        if visited[j]:
            continue
        if c == color_used:
            c += 1
        mi = min(i, j)
        ma = max(i, j)
        colors[(mi, ma)] = c
        dfs(j, adjs, visited, c, colors)
        c += 1

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

r,c,k = map(int,input().split())
lst = [[0]*c for _ in range(r)]
for i in range(k):
    a,b,v = map(int,input().split())
    lst[a-1][b-1] = v
dp = [[[0]*4 for i in range(c)] for j in range(r)]
dp[0][0][1] = lst[0][0]
for i in range(r):
    for j in range(c):
        x,y = i+1,j
        s = max(dp[i][j])
        if x < r:
            dp[x][y][0] = s
            if dp[x][y][1] < lst[x][y]+s:
                dp[x][y][1] = lst[x][y]+s
        x,y = i,j+1
        if y < c:
            if dp[i][j][2] != 0:
                if dp[x][y][3] < dp[i][j][3]:
                    dp[x][y][3] = dp[i][j][3]
                if dp[x][y][3] < dp[i][j][2]+lst[x][y] and lst[x][y] != 0:
                    dp[x][y][3] = dp[i][j][2]+lst[x][y]
            
            if dp[i][j][1] != 0:
                if dp[x][y][2] < dp[i][j][2]:
                    dp[x][y][2] = dp[i][j][2]
                if dp[x][y][2] < dp[i][j][1]+lst[x][y] and lst[x][y] != 0:
                    dp[x][y][2] = dp[i][j][1]+lst[x][y]
            
            if dp[x][y][1] < dp[i][j][1]:
                dp[x][y][1] = dp[i][j][1]
            if dp[x][y][1] < dp[i][j][0]+lst[x][y] and lst[x][y] != 0:
                dp[x][y][1] = dp[i][j][0]+lst[x][y]

            if dp[x][y][0] < dp[i][j][0]:
                dp[x][y][0] = dp[i][j][0]
print(max(dp[-1][-1]))

### FIXED CODE ###

r,c,k = map(int,input().split())
lst = [[0]*c for _ in range(r)]
for i in range(k):
    a,b,v = map(int,input().split())
    lst[a-1][b-1] = v
dp0 = [[0]*c for _ in range(r)]
dp1 = [[0]*c for _ in range(r)]
dp2 = [[0]*c for _ in range(r)]
dp3 = [[0]*c for _ in range(r)]
dp1[0][0] = lst[0][0]

for i in range(r):
    for j in range(c):
        s = max(dp0[i][j], dp1[i][j], dp2[i][j], dp3[i][j])
        x,y = i+1,j
        if x < r:
            dp0[x][y] = max(dp0[x][y], s)
            if lst[x][y]:
                dp1[x][y] = max(dp1[x][y], s+lst[x][y])
        x,y = i,j+1
        if y < c:
            dp3[x][y] = max(dp3[i][j], dp3[x][y])
            if lst[x][y]:
                dp3[x][y] = max(dp2[i][j]+lst[x][y], dp3[x][y])
            
            dp2[x][y] = max(dp2[x][y], dp2[i][j])
            if lst[x][y]:
                dp2[x][y] = max(dp2[x][y], dp1[i][j]+lst[x][y])
            
            dp1[x][y] = max(dp1[x][y], dp1[i][j])
            if lst[x][y]:
                dp1[x][y] = max(dp1[x][y], dp0[i][j]+lst[x][y])
            
            dp0[x][y] = max(dp0[x][y], dp0[i][j])
print(max(dp0[-1][-1], dp1[-1][-1], dp2[-1][-1], dp3[-1][-1]))
### BUGGY CODE ###

import math

def solve():
    N,K = map(int , input().split())
    A = list(map(int , input().split()))
    total = sum(A)
    max_a = max(A)
    search_region = min( total+1, N*max_a+1)
    
    max_d = 1
    for d in range(2, search_region):
        if total % d == 0:
            remainders = [a%d for a in A]
            remainders = sorted(remainders)
            # print(d, remainders)
            positive_rem = 0
            negative_rem = 0
            flag = True
            for rem in remainders:
                if positive_rem+rem <= K:
                    positive_rem += rem
                elif negative_rem+(d-rem) <=K:
                    negative_rem += (d-rem)
                else: 
                    flag = False
                    break

            if flag :
                # print(d, remainders, positive_rem, negative_rem)
                max_d = d
            
    print(max_d)
    
solve()

### FIXED CODE ###

def solve():
    N,K = map(int , input().split())
    A = list(map(int , input().split()))
    max_total = 22361 # sqrt(10**6 * 500)
    total = sum(A)
    search_space = set([])

    max_d = 1
    for d in range(1, min(total, max_total) ):
        if total % d == 0:
            search_space.add(d)
            search_space.add(total // d)
    
    # print(search_space)
    
    for d in search_space:
        if total % d == 0:
            remainders = [a%d for a in A]
            remainders = sorted(remainders)
            # print(d, remainders)
            positive_rem = 0
            negative_rem = 0
            flag = True
            for rem in remainders:
                if positive_rem+rem <= K:
                    positive_rem += rem
                elif negative_rem+(d-rem) <=K:
                    negative_rem += (d-rem)
                else: 
                    flag = False
                    break

            if flag and d > max_d:
                # print(d, remainders, positive_rem, negative_rem)
                max_d = d
            
    print(max_d)
    
solve()
### BUGGY CODE ###

def main():
    MOD = 10 ** 9 + 7

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

    N = len(S)

    dp = [0] * (N + 1)
    dp[0] = 1

    for i in range(K + N):
        dp[N] = (dp[N] * 26 + dp[N - 1]) % MOD
        for j in range(N - 1, 0, -1):
            dp[j] = (dp[j] * 25 + dp[j - 1]) % MOD
        dp[0] = dp[0] * 25 % MOD

    print(dp[-1])

    # for i in range(1, K + N + 1):
    #     dp[N] = (dp[N] * 26 + dp[N - 1]) % MOD
    #     x = min(i, N)
    #     for j in range(x, x - 3, -1):
    #         dp[j] = (dp[j] * 25 + dp[j - 1]) % MOD
    #     dp[0] = dp[0] * 25 % MOD
    #
    # print(dp[-2])


if __name__ == '__main__':
    main()

# sys.setrecursionlimit(10 ** 7)
# 
# (int(x)-1 for x in input().split())
# rstrip()
#
# def binary_search(*, ok, ng, func):
#     while abs(ok - ng) > 1:
#         mid = (ok + ng) // 2
#         if func(mid):
#             ok = mid
#         else:
#             ng = mid
#     return ok


### FIXED CODE ###

class Calc:
    def __init__(self, max_value, mod):
        """combination(max_value, all)"""
        fact = [-1] * (max_value + 1)
        fact[0] = 1
        fact[1] = 1
        for x in range(2, max_value + 1):
            fact[x] = x * fact[x - 1] % mod

        invs = [1] * (max_value + 1)
        invs[max_value] = pow(fact[max_value], mod - 2, mod)
        for x in range(max_value - 1, 0, -1):
            invs[x] = invs[x + 1] * (x + 1) % mod

        self.fact = fact
        self.invs = invs
        self.mod = mod

    def nCr(self, n, r):
        r = min(n - r, r)
        if r < 0: return 0
        if r == 0: return 1
        if r == 1: return n
        return self.fact[n] * self.invs[r] * self.invs[n - r] % self.mod

    def nHr(self, n, r):
        return self.nCr(n - 1 + r, r)


class PowPreCalc:
    def __init__(self, *, b, m, mod):
        """(b**m)%mod"""
        res = [1]
        t = 1
        for _ in range(m):
            t = t * b % mod
            res.append(t)
        self._res = res

    def get_pow(self, m):
        """(b**m)%mod"""
        return self._res[m]


def main():
    MOD = 10 ** 9 + 7

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

    N = len(S)

    calc = Calc(max_value=N - 1 + K, mod=MOD)

    p26 = PowPreCalc(b=26, m=K, mod=MOD)
    p25 = PowPreCalc(b=25, m=K, mod=MOD)

    ans = 0
    for tail_len in range(K + 1):
        ans = (ans
               + calc.nCr(N - 1 + K - tail_len, N - 1) * p26.get_pow(tail_len) * p25.get_pow(K - tail_len)
               ) % MOD

    print(ans)


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

n = int(input())
a = list(map(int,input().split()))
ans = []
for i in range(n):
  ans.append(a.index(i+1)+1)
ans = [str(i) for i in ans]
answer = " ".join(ans)
print(answer)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
ans = [0 for i in range(n)]
for i,vol in enumerate(a):
  ans[vol-1]=i+1
print(*ans)
### BUGGY CODE ###

# coding: utf-8
# 133C
"""
L<=i<=j<=R
(i×j)mod 2019
0≤L<R≤2×10^9
"""

L, R = map(int, input().split())

min2019 = 2019
for i in range(L, R):
    for j in range(i+1, R+1):
        #print((i * j) % 2019)
        if (i * j) % 2019 == 2019:
            break
        elif (i * j) % 2019 < min2019:
            min2019 = (i * j) % 2019
            
print(min2019)

### FIXED CODE ###

# coding: utf-8
# 133C
"""
L<=i<=j<=R
(i×j)mod 2019
0≤L<R≤2×10^9
"""

def solve(L, R):
    if R - L > 2019:
        return 0
    
    tmp = 2019
    for i in range(L, R):
        for j in range(R, i, -1):
            if (i * j) % 2019 < tmp:
                tmp = (i * j) % 2019
    return tmp
 
L, R = map(int, input().split())
print(solve(L, R))
### BUGGY CODE ###

import numpy as np
nkq = list(map(int, input().split()))

n = nkq[0]
k = nkq[1]
q = nkq[2]
aes = []
for _ in range(q):
    aes.append(int(input()))
    
    
points = np.ones(n) * k
for a in aes:
    points = points -1
    points[a-1] = points[a-1] + 1
    
    
for p in points:
    if p > 0:
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

import numpy as np
nkq = list(map(int, input().split()))


n = nkq[0]
k = nkq[1]
q = nkq[2]
aes = []
for _ in range(q):
    aes.append(int(input()))
    


points = np.zeros(n)  + (k - q)
for a in aes:
    points[a-1] = points[a-1] + 1

for p in points:
    if p > 0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

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

n, m = map(int, input().split())
adj = [[i] for i in range(n)]
for _ in range(m):
	a, b = map(int, input().split())
	adj[a-1].append(b-1)
	adj[b-1].append(a-1)

dp = [[0 for _ in range(11)] for _ in range(n)]
qs = [0]

q = int(input())
for i in range(q):
	v, d, c = map(int, input().split())
	qs.append(c)
	dp[v-1][d] = i+1

for j in range(10, 0, -1):
	for i in range(n):
		for v in adj[i]:
			dp[v][j-1] = max(dp[v][j-1], dp[i][j])

for i in range(n):
	print(qs[dp[i][0]])

### FIXED CODE ###

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

n, m = map(int, input().split())
adj = [[i] for i in range(n)]
for _ in range(m):
	a, b = map(int, input().split())
	adj[a-1].append(b-1)
	adj[b-1].append(a-1)

dp = [[0 for _ in range(11)] for _ in range(n)]
qs = [0]

q = int(input())
for i in range(q):
	v, d, c = map(int, input().split())
	qs.append(c)
	dp[v-1][d] = i+1

for j in range(10, 0, -1):
	for i in range(n):
		for v in adj[i]:
			dp[v][j-1] = max(dp[v][j-1], dp[i][j])

for i in range(n):
	print(qs[dp[i][0]])
### BUGGY CODE ###

import numpy as np
n, k = map(int, input().split())
p = [np.sum(np.arange(1, int(i) + 1)) / float(i) for i in input().split()]
p = np.array(p)
s = np.zeros(n - k + 1)
for i in range(n - k + 1):
    s[i] = np.sum(p[i: i + k])
print(s.max())

### FIXED CODE ###

import sys
n, k = map(int, input().split())
p = [int(i) for i in input().split()]
total = [0] * n
total[0] = sum(range(1, p[0] + 1)) / p[0]
max_value = 0
if k == 1:
    print(sum(range(1, max(p) + 1)) / max(p))
    sys.exit()
elif k == n:
    print(sum([sum(range(1, i + 1)) / i for i in p]))
    sys.exit()
for i in range(1, n):
    total[i] = total[i - 1] + sum(range(1, p[i] + 1)) / p[i]
    
    if i == k - 1:
        max_value = total[i]
    elif i >= k:
        max_value = max(max_value, total[i] - total[i - k])
print(max_value)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
ans = a[0]

def f(a):
    if 0 in a:
        return 0
    ans = a[0]
    for i in range(1, len(a)):
        ans *= a[i]
    if ans > 10 **18:
        return -1
    else:
        return ans

print(f(a))

### FIXED CODE ###

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

def f(a):
    ans = 1
    if 0 in a:
        return 0
    for i in a:
        ans *= i
        if ans > 1e+18:
            return -1
    return ans

print(f(a))
### BUGGY CODE ###

n, m = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]

cnt = 1
for i in range(1,n*m+1)[::-1]:
    if i in a:
        if i in b:
            cnt *= 1
        else:
            cnt *= len([0 for j in b if i < j])
            cnt %= 1000000007
    else:
        if i in b:
            cnt *= len([0 for j in a if i < j])
            cnt %= 1000000007
        else:
            cnt *= len([0 for j in b if i < j])*len([0 for j in a if i < j]) - (n*m - i)
            cnt %= 1000000007
if len(a) != len(set(a)) or len(b) != len(set(b)) :
    cnt = 0
print(cnt)


### FIXED CODE ###

from bisect import bisect
n, m = [int(i) for i in input().split()]
a = [int(i) for i in input().split()]
b = [int(i) for i in input().split()]
a.append(0)
b.append(0)
a.sort()
b.sort()
ia = 0
ib = 0
cnt = 1
for i in range(1,n*m+1)[::-1]:
    if i == a[-1]:
        if i == b[-1]:
            cnt *= 1
            a.pop(-1)
            b.pop(-1)
            ia += 1
            ib += 1
        else:
            cnt *= ib
            a.pop(-1)
            cnt %= 1000000007
            ia += 1
    else:
        if i == b[-1]:
            cnt *= ia
            b.pop(-1)
            cnt %= 1000000007
            ib += 1
        else:
            cnt *= ia*ib - (n*m - i)
            cnt %= 1000000007

print(cnt)
### BUGGY CODE ###

import numpy as np

def main():
    #1. make master list
    N = int(input())
    A = list(map(int, input().split()))

    A.append(0)
    A.insert(0,0)
    
    #2. remove i-th componet
    for i in range(1,N+1):
        A_copy = np.array(A)
        A_copy = np.delete(A_copy,i)
        
        dist_abs = sum(abs(A_copy[1:] - A_copy[:-1]))
        
        #3. output
        print(dist_abs)
    

if __name__ == "__main__":
    main()

### FIXED CODE ###

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

#2. make distance list
a.append(0)
a.insert(0,0)
costs = []

for i in range(n+1):
    costs.append(abs(a[i+1]-a[i]))

#3. calculate each cost
total = sum(costs)
for i in range(n):
    print(total - costs[i] - costs[i+1] + abs(a[i+2]-a[i]))
### BUGGY CODE ###

N,K=map(int,input().split())
p=list(map(int,input().split()))
mx = 0
p=list(map(lambda x: (1+x)/2, p))
#print(p)
for i in range(N-K+1):
  s = sum(p[i:i+K])
  #print(s)
  mx = max(s,mx)
  
print(mx)

### FIXED CODE ###

import numpy as np
N,K=map(int,input().split())
p=list(map(int,input().split()))
p=np.array(list(map(lambda x: (1+x)/2, p)))
mx_0 = np.sum(p[:K])
mx=0
#print(p)
if N!=K:
  for i in range(1,N-K+1):
    s = mx_0-p[i-1]+p[i+K-1]
    mx_0=s
    #print(s)
    mx = max(s,mx)
else:
  mx=np.sum(p)
  
print(mx)
### BUGGY CODE ###

def Solve(c,s):
    if s:
        if max(c)>4:return False
        for i in range(9):
            if c[i]>=2:
                cc=c[:]
                cc[i]-=2
                if Solve(cc,False):return True
    else:
        check=0
        for i in range(4):check+=c.count(3*i)
        if check==9:return True
        else:
            for i in range(7):
                if c[i]>=1:
                    cc=c[:]
                    for j in range(3):
                        cc[i+j]-=1
                        if cc[i+j]<0:break
                    if Solve(cc,False):return True
_in=""
while True:
    ans=[]
    try:_in="1123345567799"
    except EOFError:break
    for i in range(9):
        l=(_in+str(i+1))[::1]
        count=[l.count(str(j+1))for j in range(9)]
        if Solve(count,True):ans.append(str(i+1))
    print(0 if len(ans)==0 else " ".join(ans))

### FIXED CODE ###

def Solve(c,s):
    if s:
        if max(c)>4:return False
        for i in range(9):
            if c[i]>=2:
                cc=c[:]
                cc[i]-=2
                if Solve(cc,False):return True
    else:
        check=0
        for i in range(4):check+=c.count(3*i)
        if check==9:return True
        else:
            for i in range(7):
                if c[i]>=1:
                    cc=c[:]
                    isneg=False
                    for j in range(3):
                        cc[i+j]-=1
                        if cc[i+j]<0:
                            isneg=True
                            break
                    if isneg==False and Solve(cc,False):return True
_in=""
while True:
    ans=[]
    try:_in=input()
    except EOFError:break
    for i in range(9):
        l=(_in+str(i+1))[::1]
        count=[l.count(str(j+1))for j in range(9)]
        if Solve(count,True):ans.append(str(i+1))
    print(0 if len(ans)==0 else " ".join(ans))
### BUGGY CODE ###

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

cnt=1

for i in range(1,N):
    a=min(A)
    A.remove(min(A))
    b=min(A)
    A.remove(min(A))
    if 2*a>=b:
        cnt+=1
    else:
        cnt=1
    A.append(a+b)

print(cnt)

### FIXED CODE ###

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

su=sum(A)
cnt=1
for i in range(N-1,0,-1):
    if (su-A[i])*2<A[i]:
        break
    else:
        cnt+=1
        su=su-A[i]

print(cnt)
### BUGGY CODE ###

# coding: utf-8

from copy import deepcopy

import sys
sys.setrecursionlimit(100000)

N, X, Y = map(int, input().split())

# neighbor = {}
# for i in range(1, N):
#     neighbor[i] = [i+1]
# for i in range(X+4, Y):
#     neighbor[i] = [i-1, i+1]
# neighbor[X] = [X+1, Y]
# neighbor[Y] = [Y-1, Y+1]
# neighbor[N] = [] if Y < N else [N-1] 
# print(neighbor)

neighbor = {}
for i in range(1, X):
    neighbor[i] = [i+1]
for i in range(Y+1, N):
    neighbor[i] = [i+1]
for i in range(X+1, Y):
    neighbor[i] = [i-1, i+1]
neighbor[X] = [X+1, Y]
neighbor[Y] = [Y-1, Y+1]
neighbor[N] = [] if Y < N else [N-1]
# print(neighbor)

# print(neighbor)

# neighbor = {i: [i-1, i+1] for i in range(2, N)}
# neighbor[1] = [2]
# neighbor[N] = [N-1]
# neighbor[X].append(Y)
# neighbor[Y].append(X)

# appeared_st = set([])
appeared_st = [set([]) for _ in range(N+1)]
appeared_st[0] = 0


def rec(n, dist, s, k, appeared):
    # print(appeared_st)
    if dist == k:
        # if k == 2:
        #     input()
        if s < n and n not in appeared_st[s]:
            appeared_st[s].add(n)
            appeared_st[0] += 1
            # print(appeared_st)

    toes = [node for node in neighbor[n] if node not in appeared]
    for to in toes:
        appeared_copy = deepcopy(appeared)
        appeared_copy.add(to)
        rec(to, dist+1, s, k, appeared_copy)


for k in range(1, N):
    tmp = appeared_st[0]

    for s in range(1, N+1):
        rec(s, 0, s, k, {s})

    print(appeared_st[0] - tmp)

# print(appeared_st)
# print(len(appeared_st))
            


### FIXED CODE ###

# coding: utf-8

N, X, Y = map(int, input().split())

n_k = [0] * (N+1)

for i in range(1, N):
    for j in range(i+1, N+1):
        n_k[min(abs(j-i), abs(X-i) + 1 + abs(j-Y))] += 1

for k in range(1, N):
    print(n_k[k])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
H, N = map(int, input().split())
N_list = []
for i in range(N):
    A, B = map(int, input().split())
    N_list.append([A, B])
N_list.sort(reverse = True)

dp = [10 ** 9 for _ in range(H + 1)]
dp[0] = 0

for i in range(1, H + 1):
    for j in range(N):
        dp[i] = min(dp[i], (dp[i - N_list[j][0]] if i >= N_list[j][0] else 0) + N_list[j][1])

print(dp[-1])

### FIXED CODE ###

# E
# -*- coding: utf-8 -*-
H, N = map(int, input().split())
A_list = []
B_list = []
for i in range(N):
    A, B = map(int, input().split())
    A_list.append(A)
    B_list.append(B)

dp = [0 for _ in range(H + 1)]
dp[0] = 0

def test_func(dp, A_list, B_list, i, N):
    return(min([(dp[i - A_list[j]] if i >= A_list[j] else 0) + B_list[j] for j in range(N)]))


for i in range(1, H + 1):
    dp[i] = test_func(dp, A_list, B_list, i, N)

print(dp[-1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline

from collections import Counter
from copy import deepcopy
from heapq import heapify, heappush, heappop


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

    #n = 3 * 10 ** 5
    #a = list(range(1, n + 1))

    c = Counter(a)
    c = list(c.values())
    heapify(c)

    k_mx = len(c)

    for k in range(1, n + 1):
        if k > k_mx:
            print(0)
            continue

        cp = deepcopy(c)

        for _ in range(k_mx - k):
            cnt = heappop(cp)
            while cnt:
                mn = heappop(cp)
                cnt -= 1
                heappush(cp, mn + 1)

        ans = heappop(cp)
        print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline

from collections import Counter
from itertools import accumulate
from math import floor
from bisect import bisect_left


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

    c = Counter(a)
    c = list(c.values())

    d = Counter(c)
    d_li = [0] * (n + 1)
    for k, v in d.items():
        d_li[k] = v

    dk_acm = list(accumulate(d_li))

    kdk_acm = [0]
    for k, e in enumerate(d_li[1:], 1):
        kdk_acm.append(kdk_acm[-1] + k * e)

    def f(x):
        kdk_sm = kdk_acm[x]
        dk_sm = dk_acm[n] - dk_acm[x]

        return floor((kdk_sm + x * dk_sm) / x)

    fs = [float("inf")] + [f(x) for x in range(1, n + 1)]
    fs = fs[::-1]

    for k in range(1, n + 1):
        print(n - bisect_left(fs, k))


if __name__ == "__main__":
    main()