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

def main():
  s=input()
  q=int(input())
  for _ in [0]*q:
      query = input()
      try:
          t = int(query)
          s = s[::-1]
      except ValueError:
          t,f,c = map(str,query.split())
          if f == "1":
              s = c + s
          if f == "2":
              s = s + c
  print(s)
main()

### FIXED CODE ###

def main():
  from collections import deque
  s=input()
  q=int(input())
  turn = 2
  d=deque(s)

  for _ in [0]*q:
      query = input()
      if query[0] == "1":
          t = int(query)
          turn = 3 - turn
      else:
          t,f,c = map(str,query.split())
          if (int(f) + turn)% 2  == 0:
              d.append(c)
          else:
              d.appendleft(c)
  if turn == 2:
      print("".join(d))
  else:
      print("".join(list(d)[::-1]))
main()
### BUGGY CODE ###

N = int(input())
P = list(map(int, input().split()))
cnt = 0
for i in range(N):
    if min(P[:i+1]) == P[i]:
        cnt += 1
print(cnt)

### FIXED CODE ###

N = int(input())
P = list(map(int, input().split()))
cnt = 1
minp =P[0]
for i in range(1, N):
    if minp >= P[i]:
        cnt += 1
    minp = min(minp, P[i])
print(cnt)
### BUGGY CODE ###

n = int(input())
a_list = list(map(int, input().split()))
q = int(input())
a_sum = []
for _ in range(q):
    b,c = map(int, input().split())
    for i in sorted(a_list, reverse=True): #ここのインデックスを逆にするのがヤマ
        if i == b:
            a_list.remove(b)
            a_list.append(c) #ここで追加するとインデックスがずれるため
        #print(a_list)
    a_sum.append(sum(a_list))


for i in a_sum:
    print(i)

### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]
q = int(input())
num = [0] * 100010
b = [0] * q
c = [0] * q
for i in range(q):
    b[i], c[i] = map(int, input().split())

for i in a:
    num[i] += 1

s = sum(a)

#print(num)
#print(b)
#print(c)


for i in range(q):
    s += (c[i]-b[i])*num[b[i]]
    num[c[i]] += num[b[i]]
    #print(num)
    num[b[i]] = 0
    #print(num,"\n")
    print(s)
### BUGGY CODE ###

from collections import deque
from heapq import heappush,heappop

def ss_raw():
    return input().split()

def ints_raw():
    return list(map(int, ss_raw()))

INF = 1<<29

def main():
    H,W = ints_raw()
    DFST = [[-1 for i in range(W)]for i in range(H)]
    qu = deque()
    dirs = [[1,0,1],[0,1,1],[-1,0,1],[0,-1,1]]
    ans = 0
    for h in range(H):
        S = input()
        for w in range(W):
            if S[w]=="#":
                DFST[h][w]=0
                qu.append([h,w,0])
    while len(qu)!=0:
        cpos = qu.popleft()
        for dir in dirs:
            
            ny,nx,nt = [cpos[0]+dir[0],cpos[1]+dir[1],cpos[2]+dir[2]]
            if ny<0 or ny>=H or nx<0 or nx>=W:
                continue
            if DFST[ny][nx]!=-1:
                continue
            DFST[ny][nx]=nt
            ans = max(ans,nt)
            qu.append([ny,nx,nt])
    return ans

print(main())


### FIXED CODE ###

from collections import deque

def ss_raw():
    return input().split()

def ints_raw():
    return list(map(int, ss_raw()))

INF = 1<<29

def main():
    H,W = ints_raw()
    DFST = [[-1 for i in range(W)]for i in range(H)]
    qu = deque()
    dirs = [[1,0,1],[0,1,1],[-1,0,1],[0,-1,1]]
    ans = 0
    for h in range(H):
        S = input()
        for w in range(W):
            if S[w]=="#":
                DFST[h][w]=0
                qu.append([h,w,0])
    while len(qu)!=0:
        cpos = qu.popleft()
        for dir in dirs:
            
            ny,nx,nt = [cpos[0]+dir[0],cpos[1]+dir[1],cpos[2]+dir[2]]
            if ny<0 or ny>=H or nx<0 or nx>=W:
                continue
            if DFST[ny][nx]!=-1:
                continue
            DFST[ny][nx]=nt
            ans = max(ans,nt)
            qu.append([ny,nx,nt])
    return ans

print(main())
### BUGGY CODE ###

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


def cf(x1, x2):
    cf = []
    for i in range(1, min(x1, x2)+1):
        if x1 % i == 0 and x2 % i == 0:
            cf.append(i)
    return cf


c = cf(a, b)
d = []
for i in range(len(c)):
    for j in range(1, i):
        if c[i] % c[j] == 0:
            d.append(c[i])
            break
print(len(c) - len(d))


### FIXED CODE ###

import math


def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a


def factorize(n):
    b = 2
    fct = []
    while b * b <= n:
        while n % b == 0:
            n //= b
            fct.append(b)
        b = b + 1
    if n > 1:
        fct.append(n)
    return fct


a, b = map(int, input().split())
c = gcd(a, b)
d = factorize(c)
print(len(set(d))+1)
### BUGGY CODE ###


def solve():
    MOD = 998244353
    N, K = map(int, input().split())
    S = set()
    for i in range(K):
        _l, _r = map(int, input().split())
        _s = set(list(range(_l, _r+1)))
        S |= _s

    # dp[i] : iに到達する経路数
    dp = [0] * (N+1)
    dp[1] = 1
    for i in range(2, N+1):
        for d in S:
            if i-d > 0:
                dp[i] = (dp[i] + dp[i-d]) % MOD
    print(dp[N])


solve()


### FIXED CODE ###


def solve():
    MOD = 998244353
    N, K = map(int, input().split())
    LR_L = [[int(x) for x in input().split()] for y in range(K)]
    # S = set()
    # for i in range(K):
    #     _l, _r = map(int, input().split())
    #     _s = set(list(range(_l, _r+1)))
    #     S |= _s

    # dp[i] : iに到達する経路数
    dp = [0] * (N+1)
    dp[1] = 1
    dp[2] = -1
    for i in range(1, N+1):
        dp[i] += dp[i-1]
        dp[i] %= MOD
        # for d in S:
        #     if i-d > 0:
        #         dp[i] = (dp[i] + dp[i-d]) % MOD
        for li, ri in LR_L:
            if i + li < N+1:
                dp[i+li] += dp[i]
                dp[i+li] %= MOD
            if i + ri + 1 < N+1:
                dp[i+ri+1] -= dp[i]
                dp[i+ri+1] %= MOD
    print(dp[N])


solve()
### BUGGY CODE ###

N = int(input())
a = list(map(int, input().split()))
 
b_list = list(range(1, N+1))
c_list = []
for i in range(N):
    sr = b_list[i]
    g = int(a.count(sr))
    c_list.append(g)

for i in c_list:
    print(i)

### FIXED CODE ###

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

ans = [0]*N
for i in range(len(A)):
    tmp = A[i]
    ans[tmp-1] += 1


for a in ans:
    print(a)
### BUGGY CODE ###

h,n=map(int,input().split())
l=[]
s=0
for i in range(n):
    a,b=map(int,input().split())
    s=max(s,a)
    l.append((a,b))
dp=[10**10]*(h+s)
dp[0]=0
for i in range(h):
    for s,t in l:
        dp[i+s]=min(dp[i]+t,dp[i+s])
print(min(dp[h:]))

### FIXED CODE ###

H,N=map(int,input().split())
magic=[list(map(int,input().split())) for _ in range(N)]
maxA=max(a for a,b in magic)
DP=[0]*(H+maxA)
for i in range(1,H+maxA):
    DP[i]=min(DP[i-a]+b for a,b in magic)
print(DP[H])
### BUGGY CODE ###

import numpy as np

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

for i in range(n):
    A[i].append(1010 + i)
    for j in range(n):
        A[i][j] -= 1

#print(A)

S = np.zeros(n, dtype="int")

d = 0
for ii in range(n*n*2):
    co = 0
    i = 0
    F = np.zeros(n)
    ga = 0
    while co < n:
        aite = A[i][S[i]]
        #print(S)
        #print("aite",aite)
        if aite <= 1000 and A[aite][S[aite]] == i and F[i] == 0 and F[aite] == 0:
            #print("g", i, aite)
            S[i] += 1
            S[aite] += 1
            F[i] = 1
            F[aite] = 1
            co = 0
            ga += 1
        i += 1
        if i == n:
            i = 0
        co += 1
    d += 1
    #print("d", d)
    if ga == 0:
        if sum(S) == (n-1)*n:
            print(d-1)
        else:
            print(-1)
        break



### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input())
A = [list(map(int,input().split())) for i in range(n)]
for i in range(n):
    for j in range(n-1):
        A[i][j] -= 1

AA = [[j for j in i] for i in A]

ID = [[-1] * n for i in range(n)]
id_ = 0
for i in range(n):
    for j in range(i+1,n):
        ID[i][j] = id_
        ID[j][i] = id_
        id_ += 1

for i in range(n):
    for j in range(n-1):
        A[i][j] = ID[i][A[i][j]]

M = [[] for i in range(id_)]
IN = [0] * id_
for i in range(n):
    for j in range(n-2):
        M[A[i][j]].append(A[i][j+1])
        IN[A[i][j+1]] +=1
# print(A)
# print(M)

# 以下、トポロジカルソート

S = []
s = 0

for i in range(id_):
    if IN[i] == 0:
        S.append(i)

while s < len(S):
    for x in M[S[s]]:
        IN[x] -= 1
        # print(x,IN)
        if IN[x] == 0:
            S.append(x)
    s += 1

# print(S)

if len(S) < id_:
    print(-1)
else:
    T = [1] * id_
    for i in range(id_):
        for j in M[S[i]]:
            T[j] = max(T[j], T[S[i]] + 1)
    print(max(T))


# 以下、閉路検出(今は削除)

# V = [0] * id_
# S = [0]
# V[0] = 1

# import sys

# def visit(x):
#     if V[x] == 1:
#         print(-1)
#         sys.exit()
#     elif V[x] == 0:
#         V[x] = 1
#         for i in M[x]:
#             visit(i)
#         V[x] = 2

# for i in range(id_):
#     if V[i] == 0:
#         visit(i)
# print("heironasi")

# 閉路検出ここまで
### BUGGY CODE ###

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

def check(num,s):
    curr = 0
    num += "_"
    for k in range(len(s)):
        if num[curr] == s[k]:
            curr += 1
    if curr == 3:
        return True
    else:
        return False

def main():
    N = int(input())
    S = input()
    ans = 0
    for k in range(1000):
        t = str(k).zfill(3)
        if check(t,S) == True:
            ans += 1
    print(ans)
if __name__ == '__main__':
    main()


### FIXED CODE ###

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

def check(k,s):
    j = 0
    for i in range(len(s)):
        if k[j] == s[i]:
            j += 1
            if j == 3:
                return True
    return False

ans = 0
for k in range(1000):
    if check(str(k).zfill(3),S):
        ans += 1
print(ans)
### BUGGY CODE ###

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

h.sort(reverse=True)

for i in range(min(n,k)):
    h.pop(0)

print(sum(h))

### FIXED CODE ###

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

h.sort(reverse=True)

print(sum(h[min(n,k):]))
### BUGGY CODE ###

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10 ** 6)


def bw(i, p):
    if dp[i] != [0, 0]:
        return dp[i]
    b = w = 1
    for ii in h[i]:
        if ii in p: continue
        bwi = bw(ii, p + [ii])
        w *= (bwi[0] + bwi[1])
        b *= bwi[1]
        w %= md
        b %= md
    dp[i] = [b, w]
    return [b, w]


md = 10 ** 9 + 7
n = int(input())
if n == 1:
    print(2)
    exit()
h = {}
for _ in range(n - 1):
    a, b = map(int, input().split())
    h.setdefault(a, [])
    h.setdefault(b, [])
    h[a] += [b]
    h[b] += [a]
dp = [[0, 0] for _ in range(n + 1)]
b, w = bw(1, [1])
print((b + w) % md)


### FIXED CODE ###

import sys

input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)


def bw(i, p):
    if dp[i] != [0, 0]:
        return dp[i]
    b = w = 1
    for ii in h[i]:
        if ii == p: continue
        bwi = bw(ii,i)
        w *= (bwi[0] + bwi[1])
        b *= bwi[1]
        w %= md
        b %= md
    dp[i] = [b, w]
    return [b, w]


md = 10 ** 9 + 7
n = int(input())
if n == 1:
    print(2)
    exit()
h = {}
for _ in range(n - 1):
    a, b = map(int, input().split())
    h.setdefault(a, [])
    h.setdefault(b, [])
    h[a] += [b]
    h[b] += [a]
dp = [[0, 0] for _ in range(n + 1)]
b, w = bw(1, 1)
print((b + w) % md)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
m = min(A)
cnt = 0
for i in range(N):
  if A[N-1-i] == m and i != N - 1:
    m = min(A[:N-1-i])
    cnt += 1
  if i == N - 1:
    cnt += 1
print(cnt)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
m = N + 1
cnt = 0
for i in range(N):
  if m > A[i]:
    m = A[i]
    cnt += 1
print(cnt)
### BUGGY CODE ###

from collections import Counter
MOD = 10**9+7
n = int(input())
A = ['{:060b}'.format(a)[::-1] for a in map(int, input().split())]

A_d = []
for col in zip(*A):
    c = Counter(map(int, col))
    A_d.append(c[0]*c[1])

ans = 0
for d in range(60):
    ans = ans + A_d[d]*pow(2, d, MOD) % MOD
print(ans % MOD)



### FIXED CODE ###

MOD = 10**9+7
n = int(input())
A = ['{:060b}'.format(a)[::-1] for a in map(int, input().split())]
A_d = []
for col in zip(*A):
    zero_cnt = col.count('0')
    A_d.append(zero_cnt*(n-zero_cnt))

ans = 0
for d in range(60):
    ans = ans + A_d[d]*pow(2, d, MOD) % MOD
print(ans % MOD)
### BUGGY CODE ###

from collections import Counter

N = int(input())

check = []
ans = {}
answer = 0
for _ in range(N):
    s = Counter(input())
    if s not in check:
        check.append(s)
        ans[str(sorted(s.items(), key=lambda x:x[0]))] = 0

    else:
        ans[str(sorted(s.items(), key=lambda x:x[0]))] += 1
        answer += ans[str(sorted(s.items(), key=lambda x:x[0]))]

print(answer)

### FIXED CODE ###

from collections import Counter

N = int(input())

# check = []
# ans = {}
# answer = 0
# for _ in range(N):
#     s = Counter(input())
#     if s not in check:
#         check.append(s)
#         ans[str(sorted(s.items(), key=lambda x:x[0]))] = 0
#
#     else:
#         ans[str(sorted(s.items(), key=lambda x:x[0]))] += 1
#         answer += ans[str(sorted(s.items(), key=lambda x:x[0]))]
#
# print(answer)

ans = {}
answer = 0
for _ in range(N):
    s = "".join(sorted(input()))

    if s not in ans:
        ans[s] = 0

    else:
        ans[s] += 1
        answer += ans[s]

print(answer)
### BUGGY CODE ###

from bisect import bisect_left, bisect_right
from operator import itemgetter
import sys
input = sys.stdin.readline


def main():
    N, Q = map(int, input().split())
    constructions = [None] * N
    for i in range(N):
        S, T, X = map(int, input().split())
        constructions[i] = (S, T, X)
    D = [(int(input()), i) for i in range(Q)]
    D.sort(key=itemgetter(0))
    ans = [-1] * Q
    for S, T, X in constructions:
        l = bisect_left(D, (S-X, -1))
        r = bisect_right(D, (T-X, -1))
        for i in range(l, r):
            idx = D[i][1]
            if ans[idx] == -1 or ans[idx] > X:
                ans[idx] = X
    for a in ans:
        print(a)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from bisect import bisect_left, bisect_right
from operator import itemgetter
import sys
input = sys.stdin.readline


def main():
    N, Q = map(int, input().split())
    constructions = [None] * N
    for i in range(N):
        S, T, X = map(int, input().split())
        constructions[i] = (S, T, X)
    constructions.sort(key=itemgetter(2))
    D = [int(input()) for _ in range(Q)]
    ans = [-1] * Q
    nxt = list(range(1, Q+1))
    for S, T, X in constructions:
        l = bisect_left(D, S-X)
        r = bisect_right(D, T-X-1)
        idx = l
        while idx < r:
            if ans[idx] == -1:
                ans[idx] = X
            nidx = nxt[idx]
            nxt[idx] = max(nxt[idx], r)
            idx = nidx
    for a in ans:
        print(a)


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

[N,Q] = list(map(int,input().split()))
s = str(input())
t = []
d = []
for i in range(Q):
    [t_temp,d_temp] = list(map(str,input().split()))
    t.append(t_temp)
    d.append(d_temp)

def check_golem(ini,s,t,d):
    golem_temp = ini
    for i in range(len(t)):
        if s[golem_temp] == t[i]:
            if d[i] == 'L':
                golem_temp -= 1
            elif d[i] == 'R':
                golem_temp += 1
        if golem_temp >= len(s) or golem_temp < 0:
            golem_temp = 'dame'
            break
    return golem_temp

data = [0]*len(s)
for i in range(len(s)):
    data[i] = check_golem(i,s,t,d)
    
ans = 0
for i in range(len(s)):
    if data[i] == 'dame':
        ans += 1

print(len(s)-ans)

### FIXED CODE ###

[N,Q] = list(map(int,input().split()))
s = str(input())
magic = [input().split() for j in range(Q)]

def move_golem(ini,s,magic):
    golem_temp = ini
    for t,d in magic:
        if s[golem_temp] == t:
            if d == 'L':
                golem_temp -= 1
            elif d == 'R':
                golem_temp += 1
        if golem_temp == -1 or golem_temp == len(s):
            break
    return golem_temp

# check lower bound

def check_lower(s,magic):
    lb = -1
    ub = len(s)
    while ub - lb > 1:
        mid = (lb + ub)//2
        mid_golem_temp = move_golem(mid,s,magic)
        if mid_golem_temp == -1:
            lb = mid
        elif mid_golem_temp != -1:
            ub = mid
            
    return lb

def check_upper(s,magic):
    lb = -1
    ub = len(s)
    while ub - lb > 1:
        mid = (lb + ub)//2
        mid_golem_temp = move_golem(mid,s,magic)
        if mid_golem_temp == len(s):
            ub = mid
        elif mid_golem_temp != len(s):
            lb = mid
            
    return ub

print(check_upper(s,magic)-check_lower(s,magic)-1)
### BUGGY CODE ###

if __name__ == '__main__':
    N = int(input())
    L = list(map(int, input().split()))
    res = 0
    for i, li in enumerate(L[:-2]):
        for j, lj in enumerate(L[i+1:-1]):
            res += sum(li < lj + lk and lj < lk + li and lk < li + lj for lk in L[i+j+2:])
    print(res)



### FIXED CODE ###

import bisect


if __name__ == '__main__':
    N = int(input())
    L = sorted(list(map(int, input().split())))
    ans = 0
    for i in range(N-2):
        for j in range(i+1, N-1):
            ans += bisect.bisect_left(L, L[i]+L[j])-j-1
    print(ans)
### BUGGY CODE ###

# https://atcoder.jp/contests/agc033/tasks/agc033_a

import itertools
from collections import Counter
from collections import defaultdict
import bisect

def main():
    H, W = map(int, input().split())
    A = [list(input()) for _ in range(H)]

    que = []
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#':
                que.append((h, w))

    if len(que) == H * W:
        print(0)
        exit()

    ans = 0
    while True:
        # print(A)
        # print(len(que))
        src = que.copy()
        que = []
        for s in src:
            h = s[0]
            w = s[1]
            dx4 = [0, 0, 1, -1]
            dy4 = [1, -1, 0, 0]
            for dx, dy in zip(dx4, dy4):
                nh = h + dy
                nw = w + dx

                if 0 <= nh < H and 0 <= nw < W and A[nh][nw] == '.':
                    que.append((nh, nw))
                    A[nh][nw] = '#'

        if len(que) == 0:
            break

        ans += 1

    print(ans)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import itertools
from collections import Counter
from collections import defaultdict
from collections import deque
import bisect


def main():
    H, W = map(int, input().split())
    A = [list(input()) for _ in range(H)]

    checked = [[False] * W for _ in range(H)]
    ans = 0

    que = []
    for h in range(H):
        for w in range(W):
            if A[h][w] == '#' and not checked[h][w]:
                que.append((h, w))
                checked[h][w] = True
    while que:
        next_que = []
        while que:
            h, w = que.pop()
            dx4 = [0, 0, 1, -1]
            dy4 = [1, -1, 0, 0]

            for dx, dy in zip(dx4, dy4):
                next_h = h + dy
                next_w = w + dx
                if 0 <= next_h < H and 0 <= next_w < W and A[next_h][next_w] == '.' and not checked[next_h][next_w]:
                    A[next_h][next_w] = '#'
                    checked[h][w] = True
                    next_que.append((next_h, next_w))
        que = next_que
        if que:
            ans += 1

    print(ans)


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

N = int(input())
c = [[] for _ in range(N + 1)]
g = [[0] * (N + 1) for _ in range(N + 1)]
paths = []
for _ in range(N-1):
    a, b = map(int, input().split())
    paths.append((a, b))

for a, b in paths:
    cnt = 1
    while True:
        if cnt not in c[a] and cnt not in c[b]:
            c[a].append(cnt)
            c[b].append(cnt)
            g[a][b] = cnt
            break
        cnt += 1

print(max([max(x) for x in g]))
for a, b in paths:
    print(g[a][b])


### FIXED CODE ###

from collections import deque

N = int(input())
g = [[] for _ in range(N)]
vp = []
for _ in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    g[a].append(b)
    g[b].append(a)
    vp.append((a, b))

k = 0
d = dict()
cs = [0] * N
used = [False] * N

que = deque([])
used[0] = 1
que.appendleft(0)
while len(que) > 0:
    v = que.pop()
    k = max(k, len(g[v]))
    cur = 1
    for u in g[v]:
        if used[u]:
            continue
        if cur == cs[v]:
            cur += 1
        cs[u] = d[(u, v)] = d[(v, u)] = cur
        cur += 1
        used[u] = True
        que.appendleft(u)
print(k)
for p in vp:
    print(d[p])
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
a.sort()
b=list(map(int,input().split()))
b.sort()
c=list(map(int,input().split()))
c.sort()
ans=0
import bisect
for bb in b:
  ao=bisect.bisect(a,bb-1)
  cnta=len(a[:ao])
  cs=bisect.bisect(c,bb)
  cntc=len(c[cs:])
  ans+=cnta*cntc
print(ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
a.sort()
b=list(map(int,input().split()))
b.sort()
c=list(map(int,input().split()))
c.sort()
ans=0
import bisect
for i in range(n):
    x=bisect.bisect_left(a,b[i])
    y=bisect.bisect_right(c,b[i])
    ans+=x*(n-y)
print(ans)
### BUGGY CODE ###

N = int(input())

existed_dict = {}
max_count = 0
max_text_list = []
for _ in range(N):
    text = input()
    if text in existed_dict.keys():
        existed_dict[text] += 1
    else:
        existed_dict[text] = 1
    if existed_dict[text] == max_count:
        max_count = existed_dict[text]
        max_text_list.append(text)
    elif existed_dict[text] > max_count:
        max_count = existed_dict[text]
        max_text_list = []
        max_text_list.append(text)
    else:
        pass

for text in sorted(max_text_list):
    print(text)


### FIXED CODE ###

N = int(input())

existed_dict = {}
max_count = 0
max_text_list = []
for _ in range(N):
    text = input()
    if existed_dict.get(text):  # ここか
        existed_dict[text] += 1
    else:
        existed_dict[text] = 1
    if existed_dict[text] == max_count:
        max_count = existed_dict[text]
        max_text_list.append(text)
    elif existed_dict[text] > max_count:
        max_count = existed_dict[text]
        max_text_list = []
        max_text_list.append(text)
    else:
        pass

for text in sorted(max_text_list):  # ここ
    print(text)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

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

from collections import Counter

C=Counter(A)

LIST=sorted(C.values())
LEN=len(LIST)
SUM=sum(LIST)
BASE=[]
BASESUM=0

for k in range(1,N+1):
    if k>LEN:
        print(0)
    else:
        BASE.append(LIST[-k])
        #print(BASE)

        BASESUM+=LIST[-k]

        REST=SUM-BASESUM
        REST0=REST

        MIN=LIST[-k]
        MAX=LIST[-1]

        if MAX*k-BASESUM<=REST:
            print(SUM//k)
            continue

        while MIN!=MAX:
            mid=(MIN+MAX+1)//2
            REST=REST0

            for b in BASE[::-1]:
                if b<mid:
                    REST-=mid-b
                if REST<0 or b>=mid:
                    break

            #print(MAX,MIN,mid,REST)

            if REST>=0:
                MIN=mid
            else:
                MAX=mid-1

        print(MIN)


### FIXED CODE ###

import sys
input = sys.stdin.readline

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

from collections import Counter
from itertools import accumulate
import bisect

C=Counter(A)

LIST=sorted(C.values())
LEN=len(LIST)
SUM=[0]+list(accumulate(LIST))
MIN=0
MAX=SUM[-1]

for k in range(1,N+1):
    MIN=0
    while MIN!=MAX:
        mid=(MIN+MAX+1)//2
        x=bisect.bisect_right(LIST,mid)

        if SUM[x]+(LEN-x)*mid>=mid*k:
            MIN=mid
        else:
            MAX=mid-1

    print(MIN)