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

import sys
readline = sys.stdin.readline

def main():
    S = readline().rstrip()
    K = int(readline())
    N = len(S)
    d = {}
    for i in range(N):
        s = ''
        head = S[i]
        d.setdefault(head, set())
        for j in range(i, N):
            s += S[j]
            d[head].add(s)

    for key, val in sorted(d.items()):
        if K <= len(val):
            print(sorted(list(val))[K-1])
            return
        else:
            K -= len(val)


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
readline = sys.stdin.readline

def main():
    S = readline().rstrip()
    K = int(readline())
    N = len(S)
    d = {}
    for i in range(N):
        s = ''
        head = S[i]
        d.setdefault(head, set())
        for j in range(i, min(N, i+5)):
            s += S[j]
            d[head].add(s)

    for key, val in sorted(d.items()):
        if K <= len(val):
            print(sorted(list(val))[K-1])
            return
        else:
            K -= len(val)


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

n = int(input())
s = input()
r, g, b = [], [], []
for i in range(n):
    if s[i] == "R":
        r.append(i)
    elif s[i] == "G":
        g.append(i)
    else:
        b.append(i)
ans = len(r)*len(b)*len(g)
for i in r:
    for j in g:
        for k in b:
            a = sorted([i,j,k])
            if a[1] - a[0] == a[2] - a[1]:
                ans -= 1

print(ans)


### FIXED CODE ###

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

ans = len(r)*len(b)*len(g)
for i in r:
    for j in g:
        chk = j - i
        if chk + j in b:
            ans -= 1
        if i - chk in b:
            ans -= 1
        if (i + j)/2  in b:
            ans -= 1

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

from subprocess import call
call (('pypy3', '-c', """
import collections

h, w = map(int, input().split())
a = [list(input()) for _ in range(h)]

visited = [[-float("inf")]*w for _ in range(h)]
q = collections.deque([])

for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            q.appendleft([i, j])
            visited[i][j] = 0

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

while 0 < len(q):
    cy, cx = q.pop()
    for i in range(4):
        x = cx + dx[i]
        y = cy + dy[i]

        if x < 0 or w <= x or y < 0 or h <= y:
            continue

        if a[y][x] == "." and visited[y][x] == -float("inf"):
            visited[y][x] = visited[cy][cx] + 1
            q.appendleft([y, x])

ans = -1
for i in range(h):
    for j in range(w):
        ans = max(ans, visited[i][j])
print(ans)
"""))

### FIXED CODE ###

from subprocess import call
call (('pypy3', '-c', """
from collections import deque

def main():
    h, w = map(int, input().split())
    A = [list(input()) for _ in range(h)]
    d = [[10**9] * w for _ in range(h)]
    que = deque([])
    
    for i in range(h):
        for j in range(w):
           if A[i][j] == "#":
               que.append([i, j])
               d[i][j] = 0
           else:
               d[i][j] = 10 ** 9
            
    while que:
        x, y = que.popleft()
        dx = [1, 0, -1, 0]
        dy = [0, 1, 0, -1]
        for i in range(4): 
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < h and 0 <= ny < w and d[nx][ny] == 10**9:
                d[nx][ny] = d[x][y] + 1
                que.append([nx, ny])
    ans = 0
    for i in range(h):
        for j in range(w):
            ans = max(ans, d[i][j])
    print(ans)
    
    return
    
main()

"""))
### BUGGY CODE ###

import itertools
N,P = map(int,input().split())
A = list(map(int,input().split()))
even = [a for a in A if a%2==0]
odd = [a for a in A if a%2==1]
li0 = []
li1 = []
ans = 0
if P==0:
    for _ in range(0,len(odd)+1,2):
        li0.append(len(list(itertools.combinations(odd,_))))
    for i in range(len(even)+1):
        tmp = len(list(itertools.combinations(even,i)))
        for j in li0:
            ans += tmp*j
else:
    for _ in range(len(even)+1):
        li1.append(len(list(itertools.combinations(even,_))))
    for i in range(1,len(odd)+1,2):
        tmp = len(list(itertools.combinations(odd,i)))
        for j in li1:
            ans += tmp*j
print(ans)


### FIXED CODE ###

N,P = map(int,input().split())
A = list(map(int,input().split()))
for i in A:
    if i%2==1:
        print(2**(N-1))
        exit()
print(0 if P==1 else 2**N)
### BUGGY CODE ###

N, K = map(int, input().split())
h = list(map(int, input().split()))

dp = [0]*N

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

### FIXED CODE ###

def main2(N,h,K):
    dp = [0] * N
    for i in range(1,N):
        dp[i] = min([dp[j] + abs(h[i] - h[j]) for j in range(max(0, i-K), i)])
    return dp[-1]

N, K = map(int, input().split())
h = list(map(int, input().split()))
print(main2(N,h,K))
### BUGGY CODE ###

a,b,c=map(int,input().split())
k = 0
m = a % c
if m == 0:
  k = a
else:
  k = c-m + a
res = 0
for i in range(k,b+1,c):
  res += 1
print(res)

### FIXED CODE ###

a,b,c=map(int,input().split())
mini = 0
m = a % c
if m == 0:
  mini = a/c
else:
  mini = (c-m + a)/c
maxi = 0
M = b % c
if M == 0:
  maxi = b//c
else:
  maxi = (b-M)//c
res = int(maxi) - int(mini) + 1
print(res)
### BUGGY CODE ###

import collections

n=int(input())
a=[0]*n
for i in range(n):
  a[i]=int(input())
  
c = collections.Counter(a)
l=len(set(a))
ans=0

for i in range(l):
  a[i]=c.most_common()[i][1]
  if a[i]%2==1:
    ans+=1
print(ans)


### FIXED CODE ###

N = int(input())
dic = {}
for _ in range(N):
  A = input()
  if A in dic:
    del dic[A]
  else:
    dic[A]=0
print(len(dic))
### BUGGY CODE ###

r, g, b, n = map(int, input().split())

count = 0
for i_r in range(0,int(n/r)+1):
    if (n - r*i_r)<0:continue
    for i_g in range(0,int(n/g)+1):
        if (n - r*i_r - g*i_g)<0:continue
        if 0==((n - r*i_r - g*i_g)%b):

            count +=1

print(count)


### FIXED CODE ###

a, b, c, n = map(int, input().split())
aa =[a,b,c]
aa.sort()
r = aa[2]
g = aa[1]
b = aa[0]
 
count = 0
for i_r in range(0,int(n/r)+1):
    if (n - r*i_r)<0:continue
    for i_g in range(0,int((n-r*i_r)/g)+1):
        if (n - r*i_r - g*i_g)<0:continue
        if 0==((n - r*i_r - g*i_g)%b):
 
            count = count + 1
 
print(count)
### BUGGY CODE ###

#/usr/bin/env python3
# -*- coding: utf-8 -*-
# D-Grid and Integers

from collections import defaultdict

def readInput():
	return [int(i) for i in input().split(" ")]

(R, C) = readInput()
N = int(input())
rowIdx = list() 
colIdx = list()
grid = defaultdict(lambda:None)
rowGrid = defaultdict(list)
colGrid = defaultdict(list)
for i in range(N):
	(r, c, a) = readInput()
	r -= 1
	c -= 1
	rowGrid[r].append(c)
	colGrid[c].append(r)
	grid[(r, c)] = a 
	rowIdx.append(r)
	colIdx.append(c)

pairIdx = rowIdx.copy()	
for i in rowIdx:
	pairIdx.remove(i)
	for j in pairIdx:
		tempRow = set(rowGrid[i])
		tempPair = set(rowGrid[j])
		intersect = tempRow.intersection(tempPair)
		if (len(intersect) == 0):
			continue
		col = list(intersect)[0]
		diff = grid[(i, col)] - grid[(j, col)] 
		for m in tempRow:
			anchor = grid[(i, m)]
			anchorP = grid[(j, m)]
			if (anchorP == None and anchor < diff):
				print('No')
				exit()
			elif (anchorP != None and anchor - anchorP != diff):
				print('No')
				exit()
		for n in tempPair:
			anchor = grid[(j, n)]
			anchorP = grid[(i, n)]
			if (anchorP == None and anchor < -diff):
				print('No')
				exit()
print('Yes')

### FIXED CODE ###

from collections import defaultdict
import sys
sys.setrecursionlimit(10**6)

def ReadInput():
	return [int(i) for i in input().split(" ")]

(R, C) = ReadInput()
N = int(input())
VectorSet = set() 
Grid = defaultdict(list)
for i in range(N):
	(r, c, a) = ReadInput()
	Grid[("R", r)].append((("C", c), a))
	Grid[("C", c)].append((("R", r), a))
	VectorSet.add(("R", r))
	VectorSet.add(("C", c))

def iteration(vector):
	VectorSet.discard(vector)
	for (v, a) in Grid[vector]:
		temp = a - VectorCover[vector]
		if (v in VectorCover):
			if(temp != VectorCover[v]):
				print("No")
				exit()
		else:
			VectorCover[v] = temp
			iteration(v) 

while(len(VectorSet) != 0):
	vector = VectorSet.pop()
	VectorCover = dict() 
	VectorCover[vector] = 0
	iteration(vector)
	minR = min(a for (p, a) in VectorCover.items() if (p[0] == "R"))
	minC = min(a for (p, a) in VectorCover.items() if (p[0] == "C"))
	if (minR + minC < 0):
		print("No")
		exit()

print("Yes")
### BUGGY CODE ###

import sys
input = sys.stdin.readline
def dist(xyr,i,j):
  x,y,r=xyr[i]
  x1,y1,r1=xyr[j]
  d=max(0,((x-x1)**2+(y-y1)**2)**0.5-r-r1)
  return d

def main():
  xs,ys,xt,yt=map(int,input().split())
  n=int(input())
  xyr=[list(map(int,input().split())) for _ in range(n)]
  xyr.append([xs,ys,0])
  xyr.append([xt,yt,0])
  from heapq import heappop,heappush
  todo=[[0,n]]
  ka=set(())
  seen=[float('inf')]*(n+2)
  seen[n]=0
  while todo:
    _,v=heappop(todo)
    if v in ka:continue
    if v==n+1:
      print(seen[v])
      exit()
    ka.add(v)
    for nv in range(n+2):
      if v==nv or nv in ka:continue
      nd=dist(xyr,v,nv)
      if seen[nv]>seen[v]+nd:
        seen[nv]=seen[v]+nd
        heappush(todo,[seen[nv],nv])
if __name__=='__main__':
  main()


### FIXED CODE ###

from heapq import heappop,heappush
from math import sqrt
def distf(xyr,i,j):
  x,y,r=xyr[i]
  x1,y1,r1=xyr[j]
  d=max(0,sqrt((x-x1)**2+(y-y1)**2)-r-r1)
  return d

def main():
  xs,ys,xt,yt=map(int,input().split())
  n=int(input())
  xyr=[list(map(int,input().split())) for _ in range(n)]
  xyr.append([xs,ys,0])
  xyr.append([xt,yt,0])
  inf=float('inf')
  dist=[[inf]*(n+2) for _ in range(n+2)]
  for i in range(n+2):
    dist[i][i]=0
  for i in range(n+1):
    for j in range(i+1,n+2):
      dist[i][j]=distf(xyr,i,j)
      dist[j][i]=dist[i][j]
  seen=[inf]*(n+2)
  seen[n]=0
  mi=set(range(n+2))
  while mi:
    d,v=inf,-1
    for j in mi:
      if d>seen[j]:
        d=seen[j]
        v=j
    mi.remove(v)
    for nv in mi:
      nd=dist[v][nv]
      if seen[nv]>seen[v]+nd:
        seen[nv]=seen[v]+nd
  print(seen[n+1])
if __name__=='__main__':
  main()
### BUGGY CODE ###

# -*- coding: utf-8 -*-

def abc162d(n, s):

    r_arr = []
    g_arr = []
    b_arr = []

    for i in range(n):
        if s[i] == 'R':
            r_arr.append(i)
        elif s[i] == 'G':
            g_arr.append(i)
        else: # 'B'
            b_arr.append(i)

    min1_arr = r_arr
    min2_arr = g_arr
    max_arr = b_arr
    if len(r_arr) < len(g_arr) and len(b_arr) < len(g_arr):
        min1_arr = r_arr
        min2_arr = b_arr
        max_arr = g_arr
    elif len(g_arr) < len(r_arr) and len(b_arr) < len(r_arr):
        min1_arr = g_arr
        min2_arr = b_arr
        max_arr = r_arr

    ans = 0
    for r_i in min1_arr:
        for g_i in min2_arr:
            min_i = r_i
            max_i = g_i
            if g_i < r_i:
                min_i = g_i
                max_i = r_i
            diff = max_i - min_i
            minmin = min_i - diff
            maxmax = max_i + diff
            exists_central = (max_i + min_i) % 2
            central = (max_i + min_i) / 2

            ans += len(max_arr)

            if minmin in max_arr:
                ans -= 1
            if maxmax in max_arr:
                ans -= 1
            if exists_central == 0:
                if central in max_arr:
                    ans -= 1

    return ans

###
# main
if(__name__ == '__main__'):
    # input
    n = int(input())
    s = input()
    
    ans = abc162d(n, s)
    
    # output
    print(ans)
# else:
    # do nothing


### FIXED CODE ###

# -*- coding: utf-8 -*-

def abc162d(n, s):

    r_arr = []
    g_arr = []
    b_arr = []

    for i in range(n):
        if s[i] == 'R':
            r_arr.append(i)
        elif s[i] == 'G':
            g_arr.append(i)
        else: # 'B'
            b_arr.append(i)

    min1_arr = r_arr
    min2_arr = g_arr
    max_arr = b_arr
    if len(r_arr) < len(g_arr) and len(b_arr) < len(g_arr):
        min1_arr = r_arr
        min2_arr = b_arr
        max_arr = g_arr
    elif len(g_arr) < len(r_arr) and len(b_arr) < len(r_arr):
        min1_arr = g_arr
        min2_arr = b_arr
        max_arr = r_arr

    max_dict = dict()
    for elem in max_arr:
        max_dict[elem] = 1

    except_num = 0
    for r_i in min1_arr:
        for g_i in min2_arr:
            min_i = r_i
            max_i = g_i
            if g_i < r_i:
                min_i = g_i
                max_i = r_i
            diff = max_i - min_i
            minmin = min_i - diff
            maxmax = max_i + diff
            exists_central = (max_i + min_i) % 2

            if minmin in max_dict:
                except_num += 1
            if maxmax in max_dict:
                except_num += 1
            if exists_central == 0:
                central = (max_i + min_i) / 2
                if central in max_dict:
                    except_num += 1

    ans = len(r_arr) * len(g_arr) * len(b_arr) - except_num
    return ans

###
# main
if(__name__ == '__main__'):
    # input
    n = int(input())
    s = input()
    
    ans = abc162d(n, s)
    
    # output
    print(ans)
# else:
    # do nothing
### BUGGY CODE ###

N = int(input())
S = list(input())
ans = []
for i in range(len(S)):
  for j in range(i+1,len(S)):
    for k in range(j+1,len(S)):
      if not S[i]+S[j]+S[k] in set(ans):
      	ans.append(S[i]+S[j]+S[k])
print(len(ans))
      
      


### FIXED CODE ###

def main():
  N = int(input())
  S = tuple(input())
  ans = 0
  for i in range(1000):
    if i<10:
      cnt0= 0
      cnt1 = 0
      for j in range(N):
        if 2<=cnt0 and S[j]=="%d"%i:
          ans+=1
          break
        if S[j]=="0":
          cnt0+=1
          continue
    elif 10<=i<=99:
      cnt0=0
      cnt1=0
      cnt2=0
      i = list(str(i))
      for j in range(N):
        if 1<=cnt0 and 1<=cnt1 and S[j]=="%s"%i[1]:
          ans+=1
          break
        if S[j]=="0" and cnt0!=1:
          cnt0+=1
          continue
        if 1<=cnt0 and S[j]=="%s"%i[0]:
          cnt1 +=1
          continue
    elif 100<=i:
      cnt0=0
      cnt1=0
      cnt2=0
      i = list(str(i))
      for j in range(N):
        if 1<=cnt0 and 1<=cnt1 and S[j]=="%s"%i[2]:
          ans+=1
          #print(i)
          break
        if S[j]=="%s"%i[0] and cnt0!=1:
          cnt0+=1
          continue
        if 1<=cnt0 and S[j]=="%s"%i[1]:
          cnt1 +=1
          continue
  print(ans)
main()
### BUGGY CODE ###

from collections import Counter

n = int(input())
cnt = Counter(input().split())
c1, c2, c3 = cnt['1'], cnt['2'], cnt['3']
total = c1 + 2 * c2 + 3 * c3
dp = [[[0] * (n + 2) for _ in range(n + 2)] for _ in range(n + 2)]

for k in range(1, n + 1):
    still = n / k
    for a1 in range(k, max(-1, 2 * k - total - 1), -1):
        dpap, dpac, dpan = dp[a1 - 1], dp[a1], dp[a1 + 1]
        for a2 in range(min(k - a1, c2 + c3), max(-1, 3 * k - 2 * a1 - total - 1), -1):
            a3 = k - a1 - a2
            if a3 > c3:
                continue
            tmp = 0
            if a1:
                tmp += dpap[a2][a3] * a1
            if a2:
                tmp += dpan[a2 - 1][a3] * a2
            if a3:
                tmp += dpac[a2 + 1][a3 - 1] * a3
            dpac[a2][a3] = tmp / k + still
print(dp[c1][c2][c3])


### FIXED CODE ###

from collections import Counter

n = int(input())
cnt = Counter(input().split())
c1, c2, c3 = cnt['1'], cnt['2'], cnt['3']
total = c1 + 2 * c2 + 3 * c3
c23 = c2 + c3
dp = [[[0.0] * (c3 + 1) for _ in range(c2 + c3 + 1)] for _ in range(n + 2)]

for k in range(1, n + 1):
    still = n / k
    for a1 in range(k, max(-1, 2 * k - total - 1, k - c23 - 1), -1):
        dpap, dpac, dpan = dp[a1 - 1], dp[a1], dp[a1 + 1]
        for a2 in range(min(k - a1, c2 + c3), max(-1, 3 * k - 2 * a1 - total - 1, k - a1 - c3 - 1), -1):
            a3 = k - a1 - a2
            tmp = 0
            if a1:
                tmp += dpap[a2][a3] * a1
            if a2:
                tmp += dpan[a2 - 1][a3] * a2
            if a3:
                tmp += dpac[a2 + 1][a3 - 1] * a3
            dpac[a2][a3] = tmp / k + still
print(dp[c1][c2][c3])
### BUGGY CODE ###

N = int( input() )
A = list( map( int, input().split() ) )
#dp = [ 10**4 for x in range(N) ]
#dp[i] i+1まで数える最短のmonotonically increasing列の位置
 
for i in range(N+1) :
    if i+1 in A : 
#       dp[i]=A.index(i+1)
       A = A[A.index(i+1)+1:]
    else :
       if i == 0: 
          print( -1 )
       else:    
          print(N-i)
       exit()

### FIXED CODE ###

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

seekfor = 1
crack = 0

for i in range(N) :
    if A[i] == seekfor :
       seekfor += 1
    else : 
       crack += 1
    
if crack == N: 
    print( -1 )
else:    
    print(crack)
### BUGGY CODE ###

from math import gcd

K = int(input())
ans = 0

for a in range(1, K+1) :
  for b in range(1, K+1) :
    for c in range(1, K+1) :
      ans += gcd(gcd(a, b), c)
      
print(ans)

### FIXED CODE ###

from math import gcd
K = int(input())
ans = 0
for a in range(1, K+1) :
  for b in range(1, K+1) :
    for c in range(1, K+1) :
      ans += gcd(gcd(a, b), c)
print(ans)
### BUGGY CODE ###

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

A.sort()

R = A[0]

while True:
    C = A.copy()
    B = [A[0]] + [A[i+1] - A[i] for i in range(len(A)-1) if A[i+1] > A[i]]
    B = list(set(B))
    B.sort()
    R = min(R, B[0])
    if C == B:
        break
    elif R == 1:
        break
    else:
        A = B

print(R)


### FIXED CODE ###

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

A.sort()

R = A[0]

while True:
    C = A.copy()
    B = [A[0]] + [a for a in [A[i+1] % A[i] for i in range(len(A)-1)] if a > 0]
    B = list(set(B))
    B.sort()
    R = min(R, B[0])
    if C == B:
        break
    elif R == 1:
        break
    else:
        A = B

print(R)
### BUGGY CODE ###

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

counter = 0
for i in range(N):
    counter += int(lis[i] <= min(lis[:i+1]))
print(counter)

### FIXED CODE ###

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

counter=0
minimum = 10000000
for i in range(N):
    minimum = min([minimum,lis[i]])
    counter += int(lis[i] <= minimum)
print(counter)
### BUGGY CODE ###

from itertools import permutations 
n,m=map(int,input().split())
cost=[]
for i in range(m):
    cost.append([int(i) for i in input().split()])
clr=[]
for i in range(n):
    clr.append([int(i) for i in input().split()])
l=[i for i in range(m)]
ind=[[] for i in range(4)]
for i in range(n):
    for j in range(n):
        curr=(i+1+j+1)%3 
        ind[curr].append(clr[i][j]-1)
mini=10**9 
for i in range(m):
    for j in range(m):
        for k in range(m):
            if i==j or i==k or j==k:
                continue 
            curr=0 
            for x in ind[0]:
                curr+=cost[x][i]
            for x in ind[1]:
                curr+=cost[x][j]
            for x in ind[2]:
                curr+=cost[x][k]
            mini=min(mini,curr)
print(mini)


### FIXED CODE ###

from itertools import permutations 
n,m=map(int,input().split())
cost=[]
for i in range(m):
    cost.append([int(i) for i in input().split()])
clr=[]
for i in range(n):
    clr.append([int(i) for i in input().split()])
l=[i for i in range(m)]
ind=[[0 for j in range(m)] for i in range(4)]
for i in range(n):
    for j in range(n):
        curr=(i+1+j+1)%3 
        ind[curr][clr[i][j]-1]+=1 
mini=10**9 
for i in range(m):
    for j in range(m):
        for k in range(m):
            if i==j or i==k or j==k:
                continue 
            curr=0 
            for it in range(3): 
                for it1 in range(m): 
                    if it==0:
                        k1=i 
                    elif it==1:
                        k1=j 
                    else:
                        k1=k 
                    curr+=ind[it][it1]*cost[it1][k1] 
            mini=min(mini,curr)
print(mini)
### BUGGY CODE ###

# F

N = int(input())

list_plus = []
list_minus = []
for i in range(N):
    S = input()
    state = 0
    min_state = 0
    for s in S:
        if s == '(':
            state += 1
        else:
            state -= 1
        min_state = min(min_state, state)
    
    if state >= 0:
        list_plus.append([min_state, state])
    else:
        list_minus.append([min_state - state, -state])

list_plus.sort()
total_state_plus = 0
for min_state, state in list_plus[::-1]:
    if total_state_plus + min_state < 0:
        print('No')
        exit()
    else:
        total_state_plus += state

list_minus.sort()
total_state_minus = 0
for min_state, state in list_minus[::-1]:
    if total_state_minus + min_state < 0:
        print('No')
        exit()
    else:
        total_state_minus += state

print('Yes' if total_state_plus == total_state_minus else 'No')

### FIXED CODE ###

# F

N = int(input())

list_plus = []
list_minus = []
for i in range(N):
    S = input()
    state = 0
    min_state = 0
    for s in S:
        if s == '(':
            state += 1
        else:
            state -= 1
        min_state = min(min_state, state)
    
    if state > 0:
        list_plus.append((min_state, state))
    else:
        list_minus.append((min_state - state, -state))

def compute(arr):
    total_state = 0
    for min_state, state in arr[::-1]:
        if total_state + min_state < 0:
            print('No')
            exit()
        total_state += state
    return total_state

list_plus.sort()
total_state_plus = compute(list_plus)
list_minus.sort()
total_state_minus = compute(list_minus)

print('Yes' if total_state_plus == total_state_minus else 'No')
### BUGGY CODE ###

N = int(input())
A = [int(x) for x in input().split(" ")]

ans=0
r = 0
for i,a in enumerate(A):
    l = i
    a_xor = 0 
    while(l < len(A)):
        if (a_xor ^ A[l]) == (a_xor + A[l]):
            a_xor += A[l]
            l += 1
        else:
            break
    r = l-1
    ans += l - i
print(ans)


### FIXED CODE ###

N = int(input())
A = [int(x) for x in input().split(" ")]

ans=0
r = 0
for i,a in enumerate(A):
    if (i == 0) or (r + 1 == i):
        l = i+1
        a_xor = A[i]
    else:
        a_xor -= A[i-1]
    while(l < len(A)):
        if (a_xor ^ A[l]) == (a_xor + A[l]):
            a_xor += A[l]
            l += 1
        else:
            break
    r = l-1
    ans += l - i
print(ans)
### BUGGY CODE ###

import bisect
import sys
input = sys.stdin.readline


N = int(input())
A = list(map(int ,input().split()))
B = list(map(int ,input().split()))
C = list(map(int ,input().split()))
A.sort()
B.sort()
C.sort()
cnt = 0
for j in B:
    a_index = bisect.bisect_left(A, j)
    c_index = bisect.bisect_right(C, j)
    cnt += len(A[:a_index])*len(C[c_index:])
print(cnt)

### FIXED CODE ###

import bisect
import sys
input = sys.stdin.readline


N = int(input())
A = list(map(int ,input().split()))
B = list(map(int ,input().split()))
C = list(map(int ,input().split()))
A.sort()
B.sort()
C.sort()
cnt = 0
for j in B:
    a_index = bisect.bisect_left(A, j)
    c_index = bisect.bisect_right(C, j)
    cnt += a_index*(N-c_index)
print(cnt)
### BUGGY CODE ###

def solve():
    for n in range(1,N+1):
        cnt = 0
        for x in range(1,int(n**0.5)):
            if 6*(x**2) == n:
                cnt += 1
                break
            for y in range(x,int(n**0.5)):
                if 3*(x**2) + y**2 + 2*x*y == n:
                    cnt += 3
                    x += 1
                    break 
                for z in range(y,int(n**0.5)):
                    if x**2+y**2+z**2+x*y+y*z+z*x==n:
                        cnt += 3
                        x += 1
                        break                
        print(cnt)

if __name__=="__main__":
    N = int(input())
    solve()


### FIXED CODE ###

N = int(input())
ls = [0]*(N+2)
 
for i in range(1,151):
    for j in range(1,151):
        for k in range(1,151):
            t = i*i + j*j + k*k + i*j + j*k + k*i 
            if t <= N :
                ls[t] += 1
 
for p in range(1,N+1):
    print(ls[p])