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

import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))

# ===CODE===

eps = 10 ** (-9)


def main():
    def popcounter(n):
        cnt = 0
        if n == 0:
            return 0
        for _ in range(INF):
            tmp = bin(n).count("1")
            n = n % tmp
            cnt += 1

            if n == 0:
                return cnt

    n = ni()
    x = input()
    x_1 = x.count("1")

    num = int(x, 2)

    ans = []
    for i in range(len(x)):
        if x[len(x) - 1 - i] == "1":
            tmp_n = num - pow(2, i)
        else:
            tmp_n = num + pow(2, i)
        ans.append(popcounter(tmp_n))

    l = len(ans)
    for i in range(l - 1, -1, -1):
        print(ans[i])


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10000001)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))

# ===CODE===

eps = 10 ** (-9)


def main():
    def popcounter(n):
        cnt = 0
        if n == 0:
            return 0
        for _ in range(INF):
            tmp = bin(n).count("1")
            n = n % tmp
            cnt += 1
            if n == 0:
                return cnt

    n = ni()
    x = sys.stdin.readline()
    x_1 = x.count("1")

    num = int(x, 2)
    num1 = num % (x_1 - 1) if x_1 - 1 > 0 else 0
    num0 = num % (x_1 + 1)

    ans = []
    for i in range(n):
        if x[n - 1 - i] == "1":
            if x_1 - 1 < 1:
                ans.append(0)
                continue
            else:
                tmp_n = (num1 - pow(2, i, x_1 - 1)) % (x_1 - 1)
        else:
            tmp_n = (num0 + pow(2, i, x_1 + 1)) % (x_1 + 1)
        ans.append(popcounter(tmp_n) + 1)

    l = len(ans)
    for i in range(l - 1, -1, -1):
        print(ans[i])


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

a,b,c,k = map(int,input().split(' '))
ans=0

for i in range(k):
    if a > 0:
        a-=1
        ans+=1
    elif b > 0:
        b-=1
    else:
        ans-=1

print(ans)

### FIXED CODE ###

a,b,c,k = map(int,input().split(' '))
ans=0

if k > a:
    ans+=a
    k-=a
    if k > b:
        k-=b
        if k > c:
            ans-=c
        else:
            ans-=k
else:
    ans+= k

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

from heapq import *


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

for _ in range(m):
    b, c = map(int, input().split())
    for _ in range(b):
        a = heappop(A)
        if a < c:
            heappush(A, c)
        else:
            heappush(A, a)
            break

answer = sum(A)
print(answer)


### FIXED CODE ###

from heapq import *


n, m = map(int, input().split())
PAIRS = [[-a, -1] for a in map(int, input().split())]
heapify(PAIRS)

for _ in range(m):
    b, c = map(int, input().split())
    heappush(PAIRS, [-c, -b])

answer = 0
for _ in range(n):
    pair = heappop(PAIRS)
    answer += -pair[0]
    pair[1] += 1
    if pair[1] != 0:
        heappush(PAIRS, pair)

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

target_str = "AC"

N, Q = map(int, input().split()) 
S = input().strip()

for i in range(Q):
  l, r = map(int, input().split()) 
  print(S[l - 1: r].count(target_str))

### FIXED CODE ###

target_str = "AC"

N, Q = map(int, input().split()) 
S = input().strip()

cumsum_list = [0 for i in range(N)]

cnt = 0
for i in range(N - 1):
  if S[i: i + 2] == target_str:
    cnt += 1
  cumsum_list[i] = cnt
cumsum_list.insert(0, 0)
cumsum_list.insert(0, 0)


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

import math

n, m = map(int, input().split(' '))

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

for i in range(m):
    idx = a.index(max(a))
    a[idx] = a[idx] // 2
print(sum(a))

### FIXED CODE ###

import math
from heapq import heappush, heappop

n, m = map(int, input().split(' '))

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

h = []

for i in a:
    heappush(h, -i)

for i in range(m):
    v = heappop(h)
    heappush(h, -(-v // 2))

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

import math

# H, N = 9, 3
# ARR = [
#     [8, 3],
#     [4, 2],
#     [2, 1]
# ]
#
#
# H, N = 100, 6
# ARR = [
#     [1, 1],
#     [2, 3],
#     [3, 9],
#     [4, 27],
#     [5, 81],
#     [6, 243]
# ]
#

H, N = map(int, input().split())
ARR = []

for i in range(N):
    ARR.append(list(map(int, input().split())))


def calculate(h, n, arr):
    brr = [math.inf] * (h+1)
    brr[0] = 0

    for i in range(h + 1):
        for j in range(n):

            damage = arr[j][0]
            cost = arr[j][1]

            nextDamage = i + damage

            if nextDamage > h:
                nextDamage = h

            nextCost = min(brr[i] + cost, brr[nextDamage])

            brr[nextDamage] = nextCost

    print(brr[-1])


calculate(H, N, ARR)


### FIXED CODE ###

import math

# H, N = 9, 3
# ARR = [
#     [8, 3],
#     [4, 2],
#     [2, 1]
# ]
#
#
# H, N = 100, 6
# ARR = [
#     [1, 1],
#     [2, 3],
#     [3, 9],
#     [4, 27],
#     [5, 81],
#     [6, 243]
# ]
#

H, N = map(int, input().split())
ARR = []

for i in range(N):
    ARR.append(list(map(int, input().split())))


def calculate(h, n, arr):
    brr = [math.inf] * (h+1)
    brr[0] = 0

    for i in range(h + 1):
        for j in range(n):

            damage = arr[j][0]
            cost = arr[j][1]

            nextDamage = i + damage

            if nextDamage > h:
                nextDamage = h

            nextCost = min(brr[i] + cost, brr[nextDamage])

            brr[nextDamage] = nextCost

    print(brr[-1])


calculate(H, N, ARR)
### BUGGY CODE ###

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

d = [a[0]]
for i in range(n-1):
    d.append(a[i+1] - a[i])

d.append(-a[-1])

for i in range(n):
    s = 0
    for j in range(n+1):
        if j == i:
            s += abs(d[j] + d[j+1])
        elif j == i + 1:
            pass
        else:
            s += abs(d[j])
    print(s)

### FIXED CODE ###

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

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

d.append(abs(a[-1]))

s = sum(d)

for i in range(n):
    if i == 0:
        t = s - d[i] - d[i+1] + abs(a[i+1])
    elif i == n-1:
        t = s - d[i] - d[i+1] + abs(-a[i-1])
    else:
        t = s - d[i] - d[i+1] + abs(a[i+1] - a[i-1])
    print(t)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N=int(input())
from collections import defaultdict
d = defaultdict(int)
for i in range(N):
  S=input()
  d[S]+=1
max_k_list = [kv[0] for kv in d.items() if kv[1] == max(d.values())]
max_k_list.sort()
for a in max_k_list:
  print(a.rstrip('\n'))

### FIXED CODE ###

N=int(input())
S = [input() for i in range(N)]
S.sort()
import itertools
gr = itertools.groupby(S)
ans=[]
n=0
for key, group in gr:
  a=len(list(group))
  if a>n:
    ans=[]
    n=a
    ans.append(key)
  elif a==n:
    ans.append(key)
for a in ans:
  print(a)
### BUGGY CODE ###

n,x = map(int,input().split())
lis = list(map(int,input().split()))
ans = 0
magic = 0
for i in range(n):
    cou = lis[i]
    for m in range(1,n):
        if i + m >= n:co = i + m - n
        else:co = i + m
        cou = min(cou,lis[co]+x * max(m-magic,0))
        if cou == lis[co] + x * max(m-magic,0):magic = max(m,magic)
    ans += cou
print(ans)

### FIXED CODE ###

N, x = list(map(int, input().split()))
a = list(map(int, input().split()))
s_cost = a.copy()
cost = sum(s_cost)
for k in range(1,N):
    for i in range(N):
        if s_cost[i] > a[(i-k)%N] :
            s_cost[i] = a[(i-k)%N]
    if cost > k*x + sum(s_cost):
        cost = k*x + sum(s_cost)
    else:
        break

print(cost)
### BUGGY CODE ###

n=int(input())
A=[]
for i in range(n):
    a=int(input())
    A.append(a)
for i in range(n):
    b=A.pop(i)
    print(max(A))
    A.insert(i,b)

### FIXED CODE ###

n = int(input())
A = [int(input()) for i in range(n)]

M = max(A)
ind = A.index(M)
A[ind] = 0
M2 = max(A)


if M in A:
    for i in range(n):
        print(M)
else:
    for i in range(n):
        if A[i] == 0:
            print(M2)
        else:
            print(M)
### BUGGY CODE ###

import itertools
n = int(input())
s= input()
l=list(s)
c = list(itertools.combinations(l, 3))
ans=len(set(c))
print(ans)

### FIXED CODE ###

n = int(input())
s= input()
ans=0
for x in range(1000):
    num=str("{0:03d}".format(x))
    s1=s.find(num[0])
    if(s1!=-1):
        s2=s.find(num[1],s1+1)
        if(s2!=-1):
            s3=s.find(num[2],s2+1)
            if(s3!=-1):
                ans+=1
print(ans)
### BUGGY CODE ###

from bisect import bisect_left as bl
from math import factorial as f

def comb(a,b) :
    a,b = min(a,b),max(a,b)
    return f(b)//(f(a)*f(b-a))


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

checker = 0
ans1 = 0
ans2 = 0
for i in range(1,N) :
    T = L[:i]
    t = bl(T,L[i]//2)
    if t >= 1 :
        if abs(L[i]/2 - L[t]) < abs(L[i]/2 - L[t-1]) :
            p = t
        else :
            p = t-1
    else :
        p = 0
    q = L[p]
    r = comb(L[i],q)
    #print(r)
    if checker < r :
        checker = r
        ans1 = L[i]
        ans2 = q
print(ans1,ans2)


### FIXED CODE ###

from bisect import bisect_left as bl

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

p = L[-1]
q = bl(L,p/2)
if N == 2 :
    r = L[0]
else :
    if abs((p/2)-L[q]) < abs((p/2)-L[q-1]) :
        r = L[q]
    else :
        r = L[q-1]
print(p,r)
### BUGGY CODE ###

R,G,B,N = list(map(int,input().split()))
count = 0
for r in range(N//R+1):
    for g in range((N-R*r)//G+1):
        if (N-(R*r+G*g))%B == 0 and N-(R*r+G*g) >= 0:
            count += 1
print(count)

### FIXED CODE ###

R,G,B,N = list(map(int,input().split()))
count = 0
for r in range(N//R+1):
    for g in range((N-R*r)//G+1):
        if (N-(R*r+G*g))%B == 0 and N-(R*r+G*g) >= 0:
            count += 1
print(count)
### BUGGY CODE ###

S = input()
count = 0
dic = {}
ans = [0 for i in range(len(S))]
ind = []
for i in range(len(S)-1):
  if S[i]=='R' and S[i+1]=='L':
    ind += [i]
for i in range(len(S)):
  s = S[i]
  j = 0
  k = len(ind)-1
  if s=='R':
    while i>ind[j]:
      j+=1
    if (ind[j]-i)%2==0:
      ans[ind[j]]+=1
    else:
      ans[ind[j]+1]+=1
  if s=='L':
    while ind[k]>i:
      k -=1
    if (ind[k]-i)%2==0:
      ans[ind[k]]+=1
    else:
      ans[ind[k]+1]+=1
A = [str(i) for i in  ans]
print(' '.join(A))


### FIXED CODE ###

S = input()
count = 0
dic = {}
ans = [0 for i in range(len(S))]
ind = []
for i in range(len(S)-1):
  if S[i]=='R' and S[i+1]=='L':
    ind += [i]
j = 0
k = 0
for i in range(len(S)):
  s = S[i]
  if s=='R':
    while i>ind[j]:
      j+=1
    if (ind[j]-i)%2==0:
      ans[ind[j]]+=1
    else:
      ans[ind[j]+1]+=1
  if s=='L':
    while ind[k]<i:
      k +=1
      if k==len(ind):
        break
    k -= 1
    if (ind[k]-i)%2==0:
      ans[ind[k]]+=1
    else:
      ans[ind[k]+1]+=1
A = [str(i) for i in  ans]
print(' '.join(A))
### BUGGY CODE ###

import itertools
X,Y,Z,K = map(int,input().split())
l_a = list(map(int,input().split()))
l_b = list(map(int,input().split()))
l_c = list(map(int,input().split()))
p = itertools.product(l_a,l_b,l_c)
ans = []
for i in p:
    ans.append(sum(i))
ans.sort(reverse = True)
for j in range(K):
    print(ans[j])

### FIXED CODE ###

X,Y,Z,K=map(int,input().split())
A=[int(x) for x in input().split()]
A.sort(reverse=True)
B=[int(x) for x in input().split()]
B.sort(reverse=True)
C=[int(x) for x in input().split()]
C.sort(reverse=True)
D=[a+b for a in A for b in B]
D.sort(reverse=True)
D=D[:3000]
E=[ab+c for ab in D for c in C]
E.sort(reverse=True)
for i in range(K):
  print(E[i])
### BUGGY CODE ###

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

p = 10**6
q = [0]*N
for i in range(N):
    Sl = S[:i] if i > 0 else "0"
    Sr = S[i+1:] if i < N-1 else "0"
    q[i] = Sl.count("W") + Sr.count("E")

q.sort()

print(q[0])


### FIXED CODE ###

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

listw = [0]
for i in range(N):
    listw.append(listw[-1]+1 if S[i] == "W" else listw[-1])

liste = [0]
for i in range(N):
    liste.append(liste[-1]+1 if S[i] == "E" else liste[-1])

list = [0]*N
for i in range(N):
    list[i] = listw[i] + liste[-1] - liste[i+1 if i != N-1 else -1]

list.sort()

print(list[0])
### BUGGY CODE ###

from collections import defaultdict,deque
import sys
input=sys.stdin.readline
N,M=map(int,input().split())
G0=defaultdict(set)
G1=defaultdict(set)
Comps=[[] for i in range(N)]
for i in range(M):
  a,b,c=map(int,input().split())
  G0[(a-1,c-1)].add((b-1,c-1))
  G0[(a-1,c-1)].add((a-1,-1))
  G0[(b-1,c-1)].add((b-1,-1))
  G0[(b-1,c-1)].add((a-1,c-1))
  Comps[a-1].append(c-1)
  Comps[b-1].append(c-1)
for i in range(N):
  for c in Comps[i]:
    G1[(i,-1)].add((i,c))
def BFS(x):
  visited=defaultdict(bool)
  stack=deque([(x,-1,0)])
  while stack:
    a,c,m=stack.popleft()
    if visited[(a,c)]:
      continue
    if a==N-1 and c==-1:
      return m
    for i in G0[(a,c)]:
      if not visited[i[0]]:
        stack.appendleft((i[0],i[1],m))
    for i in G1[(a,c)]:
      if not visited[i[0]]:
        stack.append((i[0],i[1],m+1))
    visited[(a,c)]=True
  return -1

print(BFS(0))


      
    

### FIXED CODE ###

from collections import defaultdict,deque
import sys
sys.setrecursionlimit(10**6)
input=sys.stdin.readline
N,M=map(int,input().split())
if M==0:
  print(-1)
  exit()
G=defaultdict(set)
for i in range(M):
  a,b,c=map(int,input().split())
  G[a+(c<<30)].add(b+(c<<30))
  G[b+(c<<30)].add(a+(c<<30))
  G[a].add(a+(c<<30))
  G[b].add(b+(c<<30))
  G[a+(c<<30)].add(a)
  G[b+(c<<30)].add(b)
def BFS(x):
  d={}
  for k in G.keys():
    d[k]=float("inf")
  stack=deque([(x,0)])
  if x not in d:
    return -1
  while stack:
    s,m=stack.popleft()
    if s==N:
      return m
    if d[s]>m:
      d[s]=m
      if s>=(1<<30):
        for i in G[s]:
          if d[i]>10**30:
            stack.appendleft((i,m))
      else: 
        for i in G[s]:
          if d[i]>10**30:
            stack.append((i,m+1))
  return -1

print(BFS(1))
### BUGGY 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(1,(n+1)//2):
    j = 0
    while j + 2*i <= n-1:
        if len(set(s[j]+s[j+i]+s[j+2*i])) == 3:
            ans -= 1
        j += 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(1,(n+1)//2):
    j = 0
    while j + 2*i <= n-1:
        if s[j] != s[j+i] and s[j] != s[j+2*i] and s[j+i] != s[j+2*i]:
            ans -= 1
        j += 1
print(ans)
### BUGGY CODE ###

n, a = int(input()), sorted(list(map(int, input().split())))
for i in range(int(input())):
    b, c = map(int, input().split())
    for j in range(n):
        if a[j] == b:
            a[j] = c
        elif a[j] > c:
            break
    a = sorted(a)
    print(sum(a))

### FIXED CODE ###

n, a = int(input()), list(map(int, input().split()))
s = sum(a)
d = [0] * (10 ** 5 + 1)
for i in a:
    d[i] += 1
for i in range(int(input())):
    b, c = map(int, input().split())
    d[c] += d[b]
    s += (c - b) * d[b]
    print(s)
    d[b] = 0
### BUGGY CODE ###

import numpy

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

arra = numpy.array(a)

b = []
c = []
for i in range(q):
    x, y = map(int, input().split())
    b.append(x)
    c.append(y)


for j in range(q):
    numpy.place(arra, arra == b[j], c[j])
    print(sum(arra))


### FIXED CODE ###

from collections import Counter
n = int(input())
a = list(map(int, input().split()))
q = int(input())

counter = Counter(a)
sum_res = sum(a)

for i in range(q):
    b, c = map(int, input().split())
    sum_res += (c-b)*counter[b]

    counter[c] += counter[b]
    counter[b] = 0
    print(sum_res)
### BUGGY CODE ###

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

li = [None]*N

for i, a in enumerate(A):
    li[i] = [i+1, a]

ans = 0

for l in li:
    if l[::-1] in li:
        ans += 1

print(ans//2)

### FIXED CODE ###

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

ans = 0

for i in range(N):
    if (i+1)==A[A[i]-1]:
        ans += 1

print(ans//2)
### BUGGY CODE ###

from copy import deepcopy as copy
import sys
input = sys.stdin.readline

def main(): 
    N, M = list(map(int, input().split()))
    n = 2**N

    dp = [float('inf')] * n
    dp[0] = 0

    for i in range(M):
        a, b = list(map(int, input().split()))
        t = 0

        for c in list(map(int, input().split())):
            t += 2**(c-1)

        dp_next = copy(dp)

        for j in range(n):
            dp_next[j|t] = min(dp[j|t], dp_next[j|t], dp[j]+a)

        dp = copy(dp_next)
        
    ans = dp[-1]
    
    if ans == float('inf'): print(-1)
    else: print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    N, M = map(int, input().split())
    INF = float('inf')
    
    L = 2 ** N
    dp = [INF] * L
    dp_next = [INF] * L
    
    nums = [2 ** i for i in range(N)]
    
    for i in range(M):
        a, b = map(int, input().split())
        b = sum([nums[c-1] for c in list(map(int, input().split()))])            
    
        dp[b] = min(dp[b], a)
        for j in range(L):
            n = j | b
            dp_next[n] = min(dp[n], dp_next[n], dp[j]+a)
        
        for j in range(L):
            dp[j] = dp_next[j]
            
    if dp[-1] == INF: print(-1)
    else: print(dp[-1])

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

import collections
import numpy as np

# リストarrからx個の同じ長さの列を取り出す時の最大の長さ
# 発想: x個取り出す時、ある文字をx個より多く取り出して列に含むことはない
#       一方ある文字をその文字がある数よりも取り出して使うこともできない
#       つまり、min(arr.count(a), x)で、x個の同じ長さの列に使えるaの数がわかる
#       さらに、sum(min(arr.count(a),x))で、x個の同じ長さの列に使える文字の数がわかる
#       よって、sum(min(arr.count(a),x))//xで、x個の同じ長さの列の長さがわかる
#       発展的に、longest(arr,x)までの計算状況からlongest(arr,x+1)が計算できる
def longest(arr, x):    # legacy
    return sum(min(arr.count(a), x) for a in arr) // x


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

counter = collections.Counter(a)
nums = list(counter.values())
num_counter = collections.Counter(nums)
lastest_add = np.count_nonzero(nums)
building = [0]
longests = [0]
for i in range(1, n+1):
    appended = building[-1] + lastest_add
    building.append(appended)
    longests.append(appended // i)
    lastest_add -= num_counter[i]

for k in range(1, n+1):
    maxindexes = list(i for i, x in enumerate(longests) if x >= k)
    if maxindexes:
        print(max(maxindexes))
    else:
        print(0)
    


### FIXED CODE ###

import collections
import numpy as np

# リストarrからx個の同じ長さの列を取り出す時の最大の長さ
# 発想: x個取り出す時、ある文字をx個より多く取り出して列に含むことはない
#       一方ある文字をその文字がある数よりも取り出して使うこともできない
#       つまり、min(arr.count(a), x)で、x個の同じ長さの列に使えるaの数がわかる
#       さらに、sum(min(arr.count(a),x))で、x個の同じ長さの列に使える文字の数がわかる
#       よって、sum(min(arr.count(a),x))//xで、x個の同じ長さの列の長さがわかる
#       発展的に、longest(arr,x)までの計算状況からlongest(arr,x+1)が計算できる
# def longest(arr, x):    # legacy
#     return sum(min(arr.count(a), x) for a in arr) // x


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

counter = collections.Counter(a)        #O(n)
nums = list(counter.values())           #O(n)
num_counter = collections.Counter(nums) #O(n)
lastest_add = np.count_nonzero(nums)    #O(n)
building, longests = [0], [0]
for i in range(1, n+1):                 #O(n)
    appended = building[-1] + lastest_add   #O(1)
    building.append(appended)               #O(1)
    longests.append(appended // i)          #O(1)
    lastest_add -= num_counter[i]           #O(1)


lastest_longest = 0
k_most = []
for i, x in enumerate(reversed(longests)):
    while x > lastest_longest:
        lastest_longest += 1
        k_most.append(n-i)

k_most.extend([0]*(n-len(k_most)))      # zero padding

for longests_num in k_most:
    print(longests_num)

# print('----------------')
# for k in range(1, n+1):
#     maxindexes = list(i for i, x in enumerate(longests) if x >= k)
#     if maxindexes:
#         print(maxindexes[-1])
#     else:
#         print(0)
### BUGGY CODE ###

from collections import defaultdict


def factorize(n: int) -> dict:
    f = defaultdict(int)
    while n % 2 == 0:
        f[2] += 1
        n //= 2
    p = 3
    while p * p <= n:
        while n % p == 0:
            f[p] += 1
            n //= p
        p += 2
    if n != 1:
        f[n] += 1
    return f


def _pow(b, p, mod):
    ret = 1
    while p:
        if p % 2 == 1:
            ret *= b
            ret %= mod
        b **= 2
        p //= 2
    return ret


MOD = 10**9 + 7
n = int(input())
a = tuple(map(int, input().split()))

a_fac = []
lcm_fac = defaultdict(int)
for i in range(n):
    a_fac.append(factorize(a[i]))
    for k, v in a_fac[i].items():
        lcm_fac[k] = max(lcm_fac[k], v)

# print(lcm_fac)
ans = 0
for a_fac_i in a_fac:
    b_i = 1
    for k, v in lcm_fac.items():
        b_i *= _pow(k, v - a_fac_i[k], MOD)
        b_i %= MOD
    # print(i, a[i], b_i)
    ans += b_i
    ans %= MOD

print(ans)


### FIXED CODE ###

def GCD(a: int, b: int) -> int:
    return a if b == 0 else GCD(b, a % b)


def LCM(a: int, b: int) -> int:
    return a * b // GCD(a, b)


MOD = 10**9 + 7
n = int(input())
a = tuple(map(int, input().split()))

MAX_a = max(a)
iinv = [1] * (MAX_a + 1)
for i in range(2, MAX_a + 1):
    iinv[i] = MOD - iinv[MOD % i] * (MOD // i) % MOD

lcm = 1
for i in range(n):
    lcm = LCM(lcm, a[i])

lcm %= MOD

ans = 0
for i in range(n):
    ans += lcm * iinv[a[i]]
    ans %= MOD

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

s = input()
t = input()

data = [[0 for _ in range(len(t)+1)] for _ in range (len(s)+1)]

ans = ''
for i in range(1,len(s)+1) :
  for j in range(1,len(t)+1) :
    if s[i-1] == t[j-1] :
      data[i][j] = data[i-1][j-1] + 1
    else :
      data[i][j] = max(data[i-1][j] , data[i][j-1])

i = len(s)
j = len(t)

while i>0 and j>0 :
  if data[i][j] == data[i][j-1] :
    j -= 1
  elif data[i][j] == data[i-1][j] :
    i -= 1
  else :
    ans = s[i-1] + ans
    i -= 1
    j -= 1
   
print(ans)

### FIXED CODE ###

s = input()
t = input()

n = len(t) + 1
m = len(s) + 1

data = [[0 for _ in range(n)] for _ in range (m)]

ans = ''
for i in range(1,m) :
  for j in range(1,n) :
    if s[i-1] == t[j-1] :
      data[i][j] = data[i-1][j-1] + 1
    else :
      data[i][j] = max(data[i-1][j] , data[i][j-1])

i = len(s)
j = len(t)

while i>0 and j>0 :
  if data[i][j] == data[i][j-1] :
    j -= 1
  elif data[i][j] == data[i-1][j] :
    i -= 1
  else :
    ans = s[i-1] + ans
    i -= 1
    j -= 1
    
print(ans)
### BUGGY CODE ###

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

while k > 0:
    if a >= b:
        b *= 2
        k -= 1
    elif b >= c:
        c *= 2
        k -= 1

if b > a and c > b:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

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

while k > 0:
    if a >= b:
        b *= 2
        k -= 1
    else:
        c *= 2
        k -= 1

if b > a and c > b:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

import math
n=int(input())
for i in range(1,n+1):
    ans=0
    for x in range(1, math.floor(math.sqrt(i))+1):
        for y in range(1, math.floor(math.sqrt(i))+1):
            for z in range(1, math.floor(math.sqrt(i))+1):
                if x*x + y*y + z*z + x*y + y*z + z*x == i:
                    ans += 1
    print(ans)

### FIXED CODE ###

import math
N=int(input())
ans=[0 for _ in range(10**4+1)]
for x in range(1, math.floor(math.sqrt(10**4))+1):
    for y in range(1, math.floor(math.sqrt(10**4))+1):
        for z in range(1, math.floor(math.sqrt(10**4))+1):
            if x*x + y*y + z*z + x*y + y*z + z*x <= 10**4:
                ans[x*x + y*y + z*z + x*y + y*z + z*x]+=1
for i in range(1,N+1):
    print(ans[i])