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

n = int(input())
s = input()
r = []
g = []
b = []
for i in range(len(s)):
    if s[i]=="R":
        r.append(i)
    elif s[i]=="G":
        g.append(i)
    else:
        b.append(i)

# print(r)
# print(g)
# print(b)

ans = len(r)*len(g)*len(b)

for i in range(n):
    for j in range(i+1,n):
        k = j + (j-i)
        if k<n and set([s[i],s[j],s[k]])==set(["R","G","B"]):
            ans -= 1
print(ans)


### FIXED CODE ###

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

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

ans = r*g*b

for i in range(n):
    for j in range(i+1,n):
        k = j + (j-i)
        if k<n and set([s[i],s[j],s[k]])==set(["R","G","B"]):
            ans -= 1
print(ans)
### BUGGY CODE ###

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

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=[]
for i in range(n):
    ans.append([a[i], i+1])
ans.sort()
for i in ans:
    print(i[1], end=" ")
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
    u, v = map(int, input().split())
    graph[u].append(v)

S, T = map(int, input().split())
def f7(seq):
    seen = set()
    seen_add = seen.add
    return [ x for x in seq if x not in seen and not seen_add(x)]

graph_ken = [[]]
for i in range(1, N+1):
    now = i
    queue = graph[now][:]
    for _ in range(2):
        nextqueue = []
        for next in queue:
            nextqueue.extend(graph[next])
        queue = f7(nextqueue)
    graph_ken.append(queue)



queue = [S]
visit = [False for _ in range(N+1)]
visit[S] = True
ans = 0
while len(queue) > 0:
    nextqueue = []
    for now in queue:
        visit[now] = True
        for next in graph_ken[now]:
            if not visit[next]:
                nextqueue.append(next)
    queue = f7(nextqueue)
    if visit[T]:
        break
    ans += 1

if visit[T]:
    print(ans)
else:
    print(-1)


### FIXED CODE ###

import sys
from collections import deque
input = sys.stdin.readline
N, M = map(int, input().split())
graph = [[] for _ in range(N+1)]
for _ in range(M):
    u, v = map(int, input().split())
    graph[u].append(v)

S, T = map(int, input().split())

inf = 10**6
ans = [[inf, inf, inf] for i in range(N+1)]

q = deque([S])
ans[S][0] = 0
while q:
    now = q.popleft()
    for next in graph[now]:
        flag = 0
        for i in range(3):
            if ans[now][i] != inf:
                if ans[next][(i+1)%3] > ans[now][i] + 1:
                    flag = 1
                    ans[next][(i+1)%3] = ans[now][i] + 1
        if flag == 1:
            q.append(next)

if ans[T][0] == inf:
    print(-1)
else:
    print(ans[T][0]//3)
### BUGGY CODE ###

def solve(pos, tot, A):
    if tot == 0: return True
    if pos > len(A) - 1: return False

    return solve(pos+1, tot - A[pos], A) or \
           solve(pos+1, tot, A)

n = raw_input()
b = map(int, raw_input().split())
n = raw_input()
t = map(int, raw_input().split())

for tt in t:
    print 'yes' if True == solve(0, tt, b) else 'no'

### FIXED CODE ###

def solve(pos, tot, A):
    if tot == 0: return True
    if pos > len(A) - 1: return False

    return solve(pos+1, tot - A[pos], A) or \
           solve(pos+1, tot, A)

n = raw_input()
b = map(int, raw_input().split())
n = raw_input()
t = map(int, raw_input().split())

max = sum(b) + 1
for tt in t:
    print 'yes' if tt < max and True == solve(0, tt, b) else 'no'
### BUGGY CODE ###

# D - Integer Cards

from operator import itemgetter

N, M = map(int, input().split())
A = sorted([int(a) for a in input().split()])

BC = []
for i in range(M):
    b, c = map(int, input().split())
    BC.append((b, c))

BC = sorted(BC, key=itemgetter(1), reverse=True)

D = []
for _ in range(M):
    bc = BC.pop()
    D += [bc[1]] * bc[0]

for i in range(N):
    if len(D) != 0 and A[i] <= D[-1]:
        A[i] = D.pop()

print(sum(A))


### FIXED CODE ###

# D - Integer Cards

from operator import itemgetter

N, M = map(int, input().split())
A = sorted([int(a) for a in input().split()])

BC = []
for i in range(M):
    b, c = map(int, input().split())
    BC.append([b, c])

BC = sorted(BC, key=itemgetter(1), reverse=True)

ans = 0
for i in range(N):
    if len(BC) != 0 and A[i] <= BC[0][1]:
        ans += BC[0][1]
        BC[0][0] -= 1
        if BC[0][0] == 0:
            BC.pop(0)
    else:
        ans += A[i]

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

n, d = map(int, input().split())
a = list(map(int, input().split()))
c = 0
while c != d:
    c += 1
    t = a.index(max(a))
    a[t] = max(a)//2
    if max(a) == 0:
        print(sum(a))
        quit()
else:
    print(sum(a))

### FIXED CODE ###

import heapq
n, d = map(int, input().split())
a = list(map(lambda x: int(x)*(-1), input().split()))
heapq.heapify(a)

for _ in range(d):
    t = heapq.heappop(a)
    heapq.heappush(a, (-1)*(-t//2))

print(-sum(a))
### BUGGY CODE ###

[N,L] = [int(x) for x in input().split()]
A = [[int(x),int(i)] for i,x in enumerate(input().split())]
A = sorted(A)
ANS = [10**9+1]*N
for a in A:
    for i in range(L):
        try :
            if a[0] < int(ANS[a[1]+i]) :
                ANS[a[1]+i] = str(a[0])
        except IndexError : continue
print(" ".join(ANS[L-1:]))

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

import functools
import operator
N = int(input())
prod = functools.partial(functools.reduce,operator.mul)
print(prod(list(range(1,N+1)))%(10**9+7))

### FIXED CODE ###

from math import factorial
N = int(input())
print(factorial(N)%(10**9+7))
### BUGGY CODE ###

L,R = map(int,input().split())
a = []
for i in range(L,min(R,L+2019*3)+1):
    a.append(i%2019)
ans = 10**10
b = len(a)
for i in range(b):
    for j in range(b):
        if i<=j:
            break
        ans=min(ans,(a[i]*a[j])%2019)
print(ans)

### FIXED CODE ###

L,R = map(int,input().split())
a = [i for i in range(L,min(L+2019,R)+1)]
b = len(a)
ans = 10**10
for i in range(b):
    for j in range(b):
        if i==j:
            break
        ans = min(ans,a[i]*a[j]%2019)
print(ans)
### BUGGY CODE ###

from heapq import heappop, heappush, heapify
from collections import deque
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
A = [int(i) for i in input().split()]
S = []
for i in range(M):
  B,C = map(int, input().split())
  A.extend([C]*B)
A.sort()
print(sum(A[-N:]))

### FIXED CODE ###

N, M = map(int, input().split())
A = [int(i) for i in input().split()]
table = []
for i in range(N):
  table.append((A[i],1))
for i in range(M):
  b,c = map(int, input().split())
  table.append((c,b))
table.sort()
count = 0
ans = 0
while True:
  c, b = table.pop()
  if b <= N - count:
    ans += c*b
    count += b
  else:
    ans += (N-count)*c
    break
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**7)

n,x,y = map(int,input().split())

import queue
# FIFOキューの作成
q = queue.Queue()

dst = [[0 for i in range(n+1)] for j in range(n+1)]

kyori = [0] * (n+1)

#num = 1

for i in range(1,n):
    num = 1
    q.put([i,0])
    while not q.empty():
        
        kari = q.get()
        tmp = kari[0]
        tmp_dst = kari[1]
        #print(tmp[0])
        #exit()
        if tmp >= n+1:
            continue
        if tmp < 1:
            continue
        if tmp == x:
            if dst[i][y] == 0:
                kyori[tmp_dst+1] += 1
                dst[i][y] = tmp_dst+1
                q.put([y,tmp_dst+1])
                
        if tmp == y:
            if dst[i][x] == 0:
                kyori[tmp_dst+1] += 1
                dst[i][x] = tmp_dst+1
                q.put([x,tmp_dst+1])
        if tmp+1 <= n:
            if dst[i][tmp+1] == 0:
                q.put([tmp+1,tmp_dst+1])
                kyori[tmp_dst+1] += 1
                dst[i][tmp+1] = tmp_dst+1
        if tmp-1 >= 1:
            if dst[i][tmp-1] == 0:
                q.put([tmp-1,tmp_dst+1])
                kyori[tmp_dst+1] += 1
                dst[i][tmp-1] = tmp_dst+1
        
        num += 1
        #print(dst[i])
    #exit()
    #print(dst[i])

#print(kyori)
#print(dst)

kyori = [0] * (n+1)

for i in range(1,n):
    #print(dst[i],i)
    for j in range(i+1,n+1):
        #print(i,j,dst[i][j])
        kyori[dst[i][j]] += 1

#print(kyori)
#exit()

for i in range(1,n):
    print(kyori[i])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)

n,x,y = map(int,input().split())

dst = [0] * n

#print(dst)

for i in range(1,n+1):
    for j in range(i+1,n+1):
        kyori = min(j-i,abs(x-i)+abs(y-j)+1)
        dst[kyori] += 1
        #print(i,j,kyori)
        
for i in range(n-1):
    print(dst[i+1])
#print(dst)
### BUGGY CODE ###

S = input()
A,B_i,C,Q=[],[],[],[]

suma,sumc,sumq=0,0,0
for i,s in enumerate(S):
  if s=="A":
    suma+=1
  elif s=="C":
    sumc+=1
  elif s=="?":
    sumq+=1
    B_i.append(i)
  elif s=="B":
    B_i.append(i)
    
  A.append(suma)
  C.append(sumc)
  Q.append(sumq)
  
mod=10**9+7  
ans=0
for i in B_i:
  if i==0 or i==len(S):
    continue
  k=Q[-1]-Q[i]+Q[i-1]
  ans+=A[i-1]*(C[-1]-C[i])*(3**k)%mod
  ans+=Q[i-1]*(C[-1]-C[i])*(3**(k-1))%mod
  ans+=A[i-1]*(Q[-1]-Q[i])*(3**(k-1))%mod
  ans+=Q[i-1]*(Q[-1]-Q[i])*(3**(k-2))%mod
  
print(int(ans%mod))

### FIXED CODE ###

S = input()
mod=10**9+7

suma,sumc,sumq=0,0,0
maxC=S.count("C")%mod
maxQ=S.count("?")%mod
ans1,ans2,ans3,ans4=0,0,0,0

for i,s in enumerate(S):
  if s=="A":
    suma+=1
    suma%=mod
  elif s=="C":
    sumc+=1
    sumc%=mod
  elif s=="?":
    sumq+=1
    sumq%=mod
  
  if i==0 or i==len(S):
    continue
  
  if s=="?":
    ans2+=suma    *(maxC-sumc)%mod
    ans3+=(sumq-1)*(maxC-sumc)%mod
    ans3+=suma    *(maxQ-sumq)%mod
    ans4+=(sumq-1)*(maxQ-sumq)%mod
  elif s=="B":
    ans1+=suma*(maxC-sumc)%mod
    ans2+=sumq*(maxC-sumc)%mod
    ans2+=suma*(maxQ-sumq)%mod
    ans3+=sumq*(maxQ-sumq)%mod
    
ans1*=3**maxQ%mod
ans2*=3**(maxQ-1)%mod
ans3*=3**(maxQ-2)%mod
ans4*=3**(maxQ-3)%mod
ans=ans1+ans2+ans3+ans4
print(int(ans%mod))
### BUGGY CODE ###

print(sum(range(1,int(input()))))

### FIXED CODE ###

print((lambda x:int(x)*(int(x)-1)//2)(int(input())))
### BUGGY CODE ###

import heapq
def SME(start,end):
    A = []
    if end > N : end = N
    count = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] == 0:
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N * 0.995 - 50 : break
    for i in range(L):
        if ANS[i] == 0 : ANS[i] = min(Whole[:i+1])
    for i in range(L,N):
        if ANS[i] == 0 : ANS[i] = min(Whole[i+1-L:i+1])
    return ANS

[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
ANS = [0]*N
ANS = SME(0, N)
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

a = input()
n = int(input())

for i in range(n):
    q = input()
    if q[0] == "1":
        a = a[::-1]
    else:
        if q[2] == "1":
            a = q[4] + a
        else:
            a = a + q[4]
            
print(a)

### FIXED CODE ###

s = input()
n = int(input())
a = "*"
spin = 1

for i in range(n):
    q = input()
    if q[0] == "1":
        spin *= -1
        a = a[::-1]
    else:
        if q[2] == "1":
            a = q[4] + a
        else:
            a = a + q[4]
            
    if len(a) == 100:
        s = a[:a.index("*")] + s[::spin] + a[a.index("*")+1:]
        a = "*"
        spin = 1
            
print(a[:a.index("*")] + s[::spin] + a[a.index("*")+1:])
### BUGGY CODE ###

def main():
    n = int(input())
    s = [""] * n
    ans = 0
    for i in range(n):
        s[i] = SortString(input())
    for i in range(n - 1):
        for j in range(i + 1, n):
            if s[i] == s[j]:
                ans += 1
            else:
                continue
    print(ans)


def SortString(text):
    textList = []
    for i in range(len(text)):
        textList.append(text[i])
    return "".join(sorted(textList))


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n = int(input())
    s = [""] * n
    ans = 0
    for i in range(n):
        s[i] = SortString(input())
    sDictionary = {}
    for i in range(n):
        if sDictionary.get(s[i]):
            ans += sDictionary.get(s[i])
            sDictionary[s[i]] += 1
        else:
            sDictionary[s[i]] = 1
    print(ans)


def SortString(text):
    return "".join(sorted(list(text)))


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

import itertools

def main():
    N, K = map(int, input().split())
    h = []
    for i in range(N):
        h.append(int(input()))

    arr = list(itertools.permutations(h, K))
    res1 = []
    res2 = []
    ans = []
    for j in range(len(arr)):
        res1.append(sorted(arr[j]))

    for k in range(len(res1)):
        res2.append(sorted(res1[k]))

    for l in range(len(res2)):
        ans.append(res2[l][K-1] - res2[l][0])
    print(min(ans))

if __name__ == "__main__":
    main()


### FIXED CODE ###

N, K = map(int, input().split())
h = [int(input()) for i in range(N)]
h.sort()
print(min(h[i+K-1] - h[i] for i in range(N-K+1)))
### BUGGY CODE ###

# cook your dish here
# cook your dish here
n=int(input())
if n%4==0:
    print("Yes")
elif n%7==0:
    print("Yes")
else:
    p=1
    t=True
    while p<26:
        if (n-(4*p))%7 ==0:
            t=False
            print("Yes")
            break
    if t:
        print("No")


### FIXED CODE ###

n=int(input())
p=0
t=True
while p<26:
    r=n-(7*p)
    if r>=0 and r%4 ==0:
        t=False
        print("Yes")
        break
    p+=1
if t:
    print("No")
### BUGGY CODE ###

N,Q = map(int,input().split())
S = input()
z = []
for j in range(N-1):
  if S[j]=='A' and S[j+1]=='C':
    z.append(j+1)
for i in range(Q):
  l,r = map(int,input().split())
  ans = [x for x in z if x >= l and x<= r-1]
  print(len(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 ###

s = input()

l = len(s)
ans = 0
tmp = 0

for i in range(l-1):
    if s[i] == 'A':
        count = 1
        for j in range(i+1, l):
            count += 1
            if s[j] == 'Z':
                tmp = count

        ans = max(ans, tmp)

print(ans)

### FIXED CODE ###

s = input()

ans = 0
tmp = 0
flag = 0

for i, j in enumerate(s):
    if flag == 0 and j == 'A':
        tmp = i
        flag = 1
    elif flag == 1 and j == 'Z':
        ans = max(ans, i-tmp+1)
        flag = 2
    elif flag == 2:
        if j == 'Z':
            ans = max(ans, i-tmp+1)
        elif j == 'A':
            flag = 1

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

def main():
    N, K  = map(int, input().split())
    h = list(map(int, input().split()))
    dp = [10**9] * N
    dp[0] = 0

    for i in range(N):
        dp[i] = min([dp[i-j] + abs(h[i]-h[i-j]) for j in range(min(K,i)+1)])
    print(dp[N-1])

if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    N, K  = map(int, input().split())
    h = list(map(int, input().split()))
    dp = [10**9] * N
    dp[0] = 0

    for i in range(N):
        dp[i] = min([dp[i-j] + abs(h[i]-h[i-j]) for j in range(min(K,i)+1)])
    print(dp[N-1])

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

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

ans = 0
for i in range(a, b + 1):
  if i % x == 0:
    ans += 1

print(ans)

### FIXED CODE ###

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

print((b//x+1)-((a-1)//x+1))
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
ans=0
j=0
b=0
for  i in range(n):
    while j<n and b^a[j]==sum(a[i:j+1]):
        b^=a[j]
        j+=1
    ans+=j-i    
    b^=a[i]
print(ans)

### FIXED CODE ###

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

import sys
inputs = sys.stdin.readline
N, Q= map(int,inputs().split())
V = [list(map(int,inputs().split())) for p in [0]*N]

mini = 1000000001
count = 0
for q in [None]*Q:
	m = int(inputs())
	num = mini
	for v in V:
		if v[0]-v[2]<=m and m <= v[1]-v[2]-1:
			num = min(v[2],num)
	if num == mini:
		print(-1)
	else:
		print(num)


### FIXED CODE ###

import sys
from operator import itemgetter
def main():
	inputs = sys.stdin.readline
	N, Q= map(int,inputs().split())
	E = [None]*2*N
	for n in range(N):
		a,b,c = map(int,inputs().split())
		E[2*n] = (a - c, 1, c)
		E[2*n + 1] = (b - c, -1, c)
	E.sort(key=itemgetter(0))
	tuple(tuple(E))
	mini = 1000000001
	kouho = {1000000001}
	my_add = kouho.add
	my_discard = kouho.discard
	q = 0
	d = int(inputs())
	flag = False
	cont = False
	for e in E:
		while e[0] > d:
			if cont == True:
				print(mini-(mini//1000000001)*1000000002)
			else:
				mini = min(kouho)
				print(mini-(mini//1000000001)*1000000002)
			cont = True
			q = q + 1
			if q > Q-1:
				flag = True
				break
			d = int(inputs())
		if flag == True:
			break
		if e[1] == 1:
			my_add(e[2])
			if mini > e[2]:
				mini = e[2]
		elif e[1] == -1:
			my_discard(e[2])
			if mini == e[2]:
				cont = False
	for t in [None]*(Q-q):
		print(-1)
main()
### BUGGY CODE ###

import os
import sys

import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))


def test(k):
    bc = np.bincount(A)
    bc.sort()
    bc = bc[np.searchsorted(bc, 1):]
    bc = bc[::-1]
    ret = 0

    while len(bc) >= k:
        bc[:k] -= 1
        bc.sort()
        bc = bc[np.searchsorted(bc, 1):]
        bc = bc[::-1]
        ret += 1
    return ret


ans = [0] * N
for k in reversed(range(1, N + 1)):
    ans[k - 1] = test(k)
print(*ans, sep='\n')


### FIXED CODE ###

import os
import sys

# import numpy as np

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

# 解説AC
# https://twitter.com/maspy_stars/status/1185552225474498560
N = int(sys.stdin.readline())
A = list(map(int, sys.stdin.readline().split()))


def test(k):
    bc = np.bincount(A)
    bc.sort()
    bc = bc[np.searchsorted(bc, 1):]
    bc = bc[::-1]
    ret = 0

    while len(bc) >= k:
        bc[:k] -= 1
        bc.sort()
        bc = bc[np.searchsorted(bc, 1):]
        bc = bc[::-1]
        ret += 1
    return ret


def cumsum(it):
    """
    累積和
    :param collections.Iterable it:
    :return:
    """
    s = 0
    ret = []
    for a in it:
        s += a
        ret.append(s)
    return ret


C = [0] * (N + 1)
for a in A:
    C[a] += 1
C.sort()
cs = list(reversed(cumsum(reversed(C))))


def solve(k):
    cnt = N // k
    if C[-1] <= cnt:
        # 全部取れるとしていい
        # 最後に2つ以上余ると max_c <= cnt に矛盾する
        return cnt

    # S = N
    # i = 1
    # while i < k:
    #     # 最大値は毎回取ることにしてもう見ない
    #     S -= C[-i]
    #     cnt = S // (k - i)
    #     max_c = C[-i - 1]
    #     if max_c <= cnt:
    #         return cnt
    #     i += 1

    ng = 0
    ok = k
    while abs(ng - ok) > 1:
        i = (ng + ok) // 2
        s = N - cs[-i]
        cnt = s // (k - i)
        max_c = C[-i - 1]
        if max_c <= cnt:
            ok = i
        else:
            ng = i
    if ok < k:
        i = ok
        s = N - cs[-i]
        return s // (k - i)
    else:
        return 0


ans = [0] * N
for k in reversed(range(1, N + 1)):
    ans[k - 1] = solve(k)
print(*ans, sep='\n')
### BUGGY CODE ###

def main(): 
    n = int(input())

    sum = 0

    for i in range(1, n):
        sum += i

    print(sum)



if __name__ == "__main__":
    main() 

### FIXED CODE ###

def main(): 
    n = int(input())

    print(int((n-1) * n // 2))

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

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

a = []
b = []

for i in range(n):
    tmp1, tmp2 = map(int, input().split())
    a.append(tmp1)
    b.append(tmp2)

dp = [pow(10, 10)] * (h + 1)
dp[0] = 0

for k in range(n):
    for j in range(h):
        if j + a[k] <= h and dp[j + a[k]] > dp[j] + b[k]:
            dp[j + a[k]] = dp[j] + b[k]
        elif j + a[k] > h:
            if dp[h] > dp[j] + b[k]:
                dp[h] = dp[j] + b[k]

print(dp[h])


### FIXED CODE ###

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

a = [0] * n
b = [0] * n

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

magic = [float("inf")] * (h + 1)
magic[0] = 0

for i in range(n):
    for j in range(0, h + 1):
        if j + a[i] <= h:
            magic[j + a[i]] = min(magic[j + a[i]], magic[j] + b[i])
        else:
            magic[h] = min(magic[h], magic[j] + b[i])

print(magic[h])
### BUGGY CODE ###

R, C, N = map(int, input().split())
def calc(x, y):
    if x == 0 or y == C:
        return x + y
    return 2*R + 2*C - x - y
A = [None]*(2*R + 2*C)
for i in range(N):
    x1, y1, x2, y2 = map(int, input().split())
    if not ((x1 in [0, R] or y1 in [0, C]) and (x2 in [0, R] or y2 in [0, C])):
        continue
    A[calc(x1, y1)] = i
    A[calc(x2, y2)] = i

st = []
for a in A:
    if st and st[-1] == a:
        st.pop()
    elif a is not None:
        st.append(a)
print('YES' if not st else 'NO')


### FIXED CODE ###

R, C, N = map(int, input().split())
def calc(x, y):
    if x == 0 or y == C:
        return x + y
    return 2*R + 2*C - x - y
A = {}
for i in range(N):
    x1, y1, x2, y2 = map(int, input().split())
    if not ((x1 in [0, R] or y1 in [0, C]) and (x2 in [0, R] or y2 in [0, C])):
        continue
    A[calc(x1, y1)] = i
    A[calc(x2, y2)] = i

st = []
for i, a in sorted(A.items()):
    if st and st[-1] == a:
        st.pop()
    elif a is not None:
        st.append(a)
print('YES' if not st else 'NO')