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

import numpy as np
n, m = map(int, input().split())
lrc = []
for _ in range(m):
    l, r, c = map(int, input().split())
    lrc.append((r, l, c))
lrc.sort(reverse=True)

inf = 10**18
dp = np.ones(n+1, dtype=np.int32)*inf
dp[n] = 0

for r, l, c in lrc:

    for i in range(l, r):
        if dp[i] > dp[r] + c:
            dp[i] = dp[r] + c
        else:
            break

ans = -1 if dp[1] == inf else dp[1]
print(ans)


### FIXED CODE ###

n, m = map(int, input().split())
lrc = []
for _ in range(m):
    lrc.append(tuple(map(int, input().split())))
lrc.sort()

inf = 10**15
dp = [inf]*(n+1)
dp[1] = 0

for l, r, c in lrc:
    for i in range(r, l, -1):
        if dp[i] > dp[l] + c:
            dp[i] = dp[l] + c
        else:
            break

ans = -1 if dp[n] == inf else dp[n]
print(ans)
### BUGGY CODE ###

def main():
    n, k = map(int, input().split())
    X, Y = [], []
    for _ in range(n):
        x, y = map(int, input().split())
        X.append(x)
        Y.append(y)
    x_min, x_max = min(X), max(X)
    y_min, y_max = min(Y), max(Y)
    res = abs(x_max - x_min) * abs(y_max - y_min)

    for x1 in range(n):
        for x2 in range(n):
            for y1 in range(n):
                for y2 in range(n):
                    lx, rx = X[x1], X[x2]
                    by, uy = Y[y1], Y[y2]
                    cnt = 0
                    for i in range(n):
                        if lx <= X[i] <= rx and by <= Y[i] <= uy:
                            cnt += 1
                    if cnt >= k:
                        res = min(res, abs(rx - lx) * abs(uy - by))
    print(res)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline


def main():
    n, k = map(int, input().split())
    X, Y = [], []
    for _ in range(n):
        x, y = map(int, input().split())
        X.append(x)
        Y.append(y)
    X_s = sorted(X)
    Y_s = sorted(Y)
    f_inf = float("inf")
    res = f_inf

    for x1 in range(n):
        for x2 in range(x1 + 1, n):
            for y1 in range(n):
                for y2 in range(y1 + 1, n):
                    lx, rx = X_s[x1], X_s[x2]
                    by, uy = Y_s[y1], Y_s[y2]
                    cnt = 0
                    for i in range(n):
                        if lx <= X[i] <= rx and by <= Y[i] <= uy:
                            cnt += 1
                    if cnt >= k:
                        res = min(res, abs(rx - lx) * abs(uy - by))
    print(res)


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

N, K = map(int, input().split())
tmp = input().split(' ')
A = []

for i in range(N):
    A = A + [int(tmp[i])]
Z = [N]*N

while K > 0 and A != Z:
    K = K - 1
    B = [0]*(N+1)
    for i in range(N):
        l = max(0,i-A[i])
        r = min(N-1,i+A[i])
        B[l]+=1
        B[r+1]-=1

    for i in range(1,N):
        B[i]+=B[i-1]
        
    A = B[0:N]

        
print(' '.join(map(str,A)))

### FIXED CODE ###

def main():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    Z = [N]*N

    while K > 0 and A != Z:
        K-=1
        B = [int(0)]*(N+1)
        for i in range(N):
            B[max(int(0),i-A[i])]+=1
            B[min(N-1,i+A[i])+1]-=1
        for i in range(1,N):
            B[i]+=B[i-1]

        A = B[0:N]

    print(' '.join(map(str,A)))

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

#!/usr/bin/env python3

from typing import Iterable


def main() -> None:
    N = ri()
    A = rmi()
    max_A = max(A)
    num = tuple(range(1, N + 1))
    cand = 0
    for a in range(N):
        a_height = A[a]
        possible_range = max_A + a_height
        for b in range(a + 1, min(a + 1 + possible_range, N)):
            diff_num = b - a
            sum_height = A[a] + A[b]
            if diff_num == sum_height:
                cand += 1
    w(cand)


def r() -> str:
    return input().strip()


def ri() -> int:
    return int(r())


def rmi(delim: str = ' ') -> int:
    return tuple(map(int, input().split(delim)))


def w(data) -> None:
    print(data)


def wm(data: Iterable) -> None:
    print(' '.join(list(map(str, data))))


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3

from typing import Iterable


def main() -> None:
    N = ri()
    A = rmi()
    num = tuple(range(1, N + 1))
    cand = 0
    log = {}
    for i in range(0, N):
        if i + 1 - A[i] in log:
            cand += log[i + 1 - A[i]]
        if i + 1 + A[i] in log:
            log[i + 1 + A[i]] += 1
        else:
            log[i + 1 + A[i]] = 1
    w(cand)


def r() -> str:
    return input().strip()


def ri() -> int:
    return int(r())


def rmi(delim: str = ' ') -> int:
    return tuple(map(int, input().split(delim)))


def w(data) -> None:
    print(data)


def wm(data: Iterable) -> None:
    print(' '.join(list(map(str, data))))


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

N=int(input())
a=list(map(int,input().split()))
ans=1
for x in a:
    ans*=x

if ans>10**18:
    print(-1)
else:
    print(ans)


### FIXED CODE ###

N=int(input())
a=list(map(int,input().split()))
flag=0
ans=1
if min(a)==0:
    ans=0
else:
    for x in a:
        ans*=x
        if ans>10**18:
            flag=1
            break
if flag==1:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

import math
#-------------
K, S = map(int, input().split())
#-------------
cnt = 0

for X in range(K+1):
  for Y in range(K+1):
    for Z in range(K+1):
      if S-(X+Y+Z) == 0:
        cnt += 1
print(cnt)

### FIXED CODE ###

import math
#-------------
K, S = map(int, input().split())
#-------------
cnt = 0

for X in range(K+1):
  for Y in range(K+1):
      if 0 <= S-(X+Y) <= K:
        cnt += 1
print(cnt)
### BUGGY CODE ###

I=lambda:map(int,input().split())
n,q=I()
s=[1]
d=[0]*-~n
f=[0,0]+s*n
e=[[]for _ in d]
while~-n:n-=1;a,b=I();e[a]+=b,;e[b]+=a,
while q:q-=1;p,x=I();d[p]+=x
while s:
 v=s.pop()
 for w in e[v]:d[w]+=d[v]*f[w];s+=[w]*f[w];f[w]=0
print(*d[1:])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
def dfs(v):
    for w in e[v]:
        if root[w]>=0:continue
        root[w]=v
        dfs(w)
def dfs2(v):
    for w in e[v]:
        if f[w]:continue
        f[w]=1
        data[w]+=data[v]
        dfs2(w)
input=sys.stdin.readline
n,q=map(int,input().split())
e=[[]for _ in range(n)]
root=[0]+[-1]*(n-1)
data=[0]*n
for _ in range(n-1):
    a,b=map(int,input().split())
    e[a-1]+=b-1,
    e[b-1]+=a-1,
#dfs(0)
for _ in range(q):
    p,x=map(int,input().split())
    data[p-1]+=x
f=[1]+[0]*(n-1)
dfs2(0)
print(*data)
### BUGGY CODE ###

n = int(input())

steps = []

for x in range(n):
    if n % (x + 1) == 0:
        steps.append(x + n // (x + 1) - 1)

print(min(steps))

### FIXED CODE ###

n = int(input())

steps = []

for x in range(int(n ** 0.5)):
    if n % (x + 1) == 0:
        steps.append(x + n // (x + 1) - 1)

print(min(steps))
### BUGGY CODE ###

n = int(input())
s = input()
q = int(input())
k = list(map(int, input().split()))
for ki in k:
    ans = 0
    DMC = [0]*3
    for i in range(n):
        c = s[i]
        if c == "D":
            DMC[0] += 1
        elif c == "M":
            DMC[1] += 1
            DMC[2] += DMC[0]
        elif c == "C":
            ans += DMC[2]
        if i >= ki-1:
            j = i-ki+1
            if s[j] == "D":
                DMC[0] -= 1
                DMC[2] -= DMC[1]
            elif s[j] == "M":
                DMC[1] -= 1
    print(ans)

### FIXED CODE ###

# コピペ https://atcoder.jp/contests/dwacon5th-prelims/submissions/7670569
# 自分の https://atcoder.jp/contests/dwacon5th-prelims/submissions/7822126
# とほぼ変わらないのに自分のものはTLEするので検証
n=int(input())
s=input()
q=int(input())
for i in list(map(int,input().split())):
    a=0
    v=[0,0,0]
    for j in range(n):
        if s[j]=="D":
            v[0]+=1
        elif s[j]=="M":
            v[1]+=1
            v[2]+=v[0]
        if j>=i:
            if s[j-i]=="D":
                v[0]-=1
                v[2]-=v[1]
            elif s[j-i]=="M":
                v[1]-=1
        if s[j]=="C":
            a+=v[2]
    print(a)
### BUGGY CODE ###

def main():
    N, K = map(int, input().split())
    XY = [tuple(map(int, input().split())) for _ in range(N)]
    XY.sort()
    XY = tuple(XY)

    def count(x_min, x_max, y_min, y_max, i, j):
        OK = 0
        # NG = 0
        for m, n in XY[i:j + 1]:
            if y_min <= n <= y_max:
                OK += 1
        if OK >= K:
            return True
        return False

    ans = 10 ** 20
    for i, val_i in enumerate(XY[:N - 1]):
        a = val_i[0]
        for j in range(i + K - 1, N):
            b = XY[j][0]
            e = b - a
            # print (e, i, j)
            for k, c in XY:
                # c = k[1]
                for l, d in XY:
                    # d = l[1]
                    if c < d:
                        if count(a, b, c, d, i, j):
                            # print ('A')
                            ans = min(ans, e * (d - c))
    print (ans)
    return

if __name__ == '__main__':
    main()


### FIXED CODE ###

#PythonだとTLEする
N, K = map(int, input().split())
X = [0] * N
Y = [0] * N
for i in range(N):
    x, y = map(int, input().split())
    X[i] = x
    Y[i] = y

def count(x_min, x_max, y_min, y_max):
    cnt = 0
    for i in range(N):
        if x_min <= X[i] <= x_max and y_min <= Y[i] <= y_max:
            cnt += 1
    return cnt

ans = 10 ** 20
for i in range(N):
    for j in range(N):
        for k in range(N):
            for l in range(N):
                # print ('i, j , k, l = ', i, j, k, l)
                if X[i] < X[j] and Y[k] < Y[l]:
                    if count(X[i], X[j], Y[k], Y[l]) >= K:
                        # print ('A')
                        ans = min(ans, (X[j] - X[i]) * (Y[l] - Y[k]))
print (ans)
### BUGGY CODE ###

def solve():
    N,K = map(int,input().split())
    A = list(map(int,input().split()))
    for k in range(K):
        imos = [0] * (N+1)
        for i,a in enumerate(A):
            l = max(0, i-a)
            r = min(N, i+1+a)
            imos[l] += 1
            imos[r] -= 1
        imos[0] = min(N, imos[0])
        for i in range(N):
            imos[i+1] = min(N, imos[i] + imos[i+1])
        A = imos[:-1]
        if A[0] == A[-1] == N:
            break
    print(*A)
solve()

### FIXED CODE ###

N,K = map(int,input().split())
A = list(map(int,input().split()))
for k in range(K):
    imos = [0] * (N+1)
    for i,a in enumerate(A):
        l = max(0, i-a)
        r = min(N, i+1+a)
        imos[l] += 1
        imos[r] -= 1
    imos[0] = min(N, imos[0])
    for i in range(N):
        imos[i+1] = min(N, imos[i] + imos[i+1])
    A = imos[:-1]
    if all(a==N for a in A):
        break
print(*A)
### BUGGY CODE ###

n=int(input())
lists=list(map(int,input().split()))
length=61
use=[0 for i in range(61)]
for  j in range(n):
    k=format(lists[j],"0%ib"%length)
    k=k[::-1]
    for some in range(len(k)):
        use[some]+=int(k[some])
answer=0
for j in range(61):
    answer+=(2**j)*use[j]*(n-use[j])%(10**9+7)
print(answer%(10**9+7))

### FIXED CODE ###

n=int(input())
lists=list(map(int,input().split()))
length=61
use=[0 for i in range(61)]
a,b=divmod(n,9)
anslist=[0 for i in range(a+1)]
for  j in range(n):
    k=format(lists[j],"0%ib"%length)
    k=k[::-1]
    p,q=divmod(j,9)
    if p>a:
        anslist.append(str(k))
    else:
        anslist[p]+=int(k)
answer=0
for some in anslist:
    some=str(some)
    some=some.zfill(61)
    for j in range(61):
        if int(some[j])!=0:
            use[j]+=int(some[j])

for j in range(61):
    answer+=(2**j)*use[j]*(n-use[j])%(10**9+7)
print(answer%(10**9+7))
### BUGGY CODE ###

# from collections import deque
H, W = list(map(int, input().split()))
# dp = [[1000 for _ in range(W)] for _ in range(H)]

S = [['#']*(W+2)] + [['#']+list(input())+['#'] for h in range(H)] + [['#']*(W+2)]
# S = (H+2, W+2)
# S =  [input().split() for h in range(H)]
max_n = 0

for h1 in range(1,H+1):
  for w1 in range(1,W+1):
    if S[h1][w1] == '#':
      continue
    distance = [[1000 for _ in range(W+2)] for _ in range(H+2)]
    distance[h1][w1] = 0
    que = []
    que.append([h1,w1])
    que_i = 0
    while que_i < len(que):
      h, w = que[que_i]
      if S[h-1][w] == '.' and [h-1, w] not in que:
        que.append([h-1,w])
        distance[h-1][w] = min(distance[h][w] + 1, distance[h-1][w])
      if S[h+1][w] == '.' and [h+1, w] not in que:
        que.append([h+1,w])
        distance[h+1][w] = min(distance[h][w] + 1, distance[h+1][w])
      if S[h][w-1] == '.' and [h, w-1] not in que:
        que.append([h,w-1])
        distance[h][w-1] = min(distance[h][w] + 1, distance[h][w-1])
      if S[h][w+1] == '.' and [h-1, w+1] not in que:
        que.append([h,w+1])
        distance[h][w+1] = min(distance[h][w] + 1, distance[h][w+1])
      que_i += 1
    hw_max_n = 0
    for h2 in range(1,H+1):
      for w2 in range(1,W+1):
        if distance[h2][w2] != 1000:
          hw_max_n = max(hw_max_n, distance[h2][w2])
    max_n = max(max_n, hw_max_n)
print(max_n)

### FIXED CODE ###

# from collections import deque
H, W = list(map(int, input().split()))
# dp = [[1000 for _ in range(W)] for _ in range(H)]

S = [['#']*(W+2)] + [['#']+list(input())+['#'] for h in range(H)] + [['#']*(W+2)]
# S = (H+2, W+2)
# S =  [input().split() for h in range(H)]
max_n = 0

for h1 in range(1,H+1):
  for w1 in range(1,W+1):
    if S[h1][w1] == '#':
      continue
    distance = [[1000 for _ in range(W+2)] for _ in range(H+2)]
    done_que = [[0 for _ in range(W+2)] for _ in range(H+2)]
    distance[h1][w1] = 0
    que = []
    que.append([h1,w1])
    que_i = 0
    while que_i < len(que):
      h, w = que[que_i]
      if S[h-1][w] == '.' and done_que[h-1][w] == 0:
        done_que[h-1][w] = 1
        que.append([h-1,w])
        distance[h-1][w] = min(distance[h][w] + 1, distance[h-1][w])
      if S[h+1][w] == '.' and done_que[h+1][w] == 0:
        done_que[h+1][w] = 1
        que.append([h+1,w])
        distance[h+1][w] = min(distance[h][w] + 1, distance[h+1][w])
      if S[h][w-1] == '.' and done_que[h][w-1] == 0:
        done_que[h][w-1] = 1
        que.append([h,w-1])
        distance[h][w-1] = min(distance[h][w] + 1, distance[h][w-1])
      if S[h][w+1] == '.' and done_que[h][w+1] == 0:
        done_que[h][w+1] = 1
        que.append([h,w+1])
        distance[h][w+1] = min(distance[h][w] + 1, distance[h][w+1])
      que_i += 1
    hw_max_n = 0
    for h2 in range(1,H+1):
      for w2 in range(1,W+1):
        if distance[h2][w2] != 1000:
          hw_max_n = max(hw_max_n, distance[h2][w2])
    max_n = max(max_n, hw_max_n)
print(max_n)
### BUGGY CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
d=[]
for i in range(m):
  b,c = map(int,input().split()) 
  a.extend([c]*b)
a.sort(reverse=True)
print(sum(a[:n]))

### FIXED CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
bc=[list(map(int,input().split())) for i in range(m)]
bc.sort(key=lambda x:x[1])
for b,c in bc[::-1]:
  a.extend([c]*b)
  if len(a)>2*n:
    break
a.sort(reverse=True)
print(sum(a[:n]))
### BUGGY CODE ###

n = int(input())
total = 0
for i in range(len(str(n))):
    total += int(str(n)[i])

if total %9 == 0:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

n = int(input())
total = 0

for i in str(n):
    total += int(i)

if total %9 == 0:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

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

cum_sum = [sum(A[:i+1]) for i in range(len(A))]
b = cum_sum[-1]

ans = float("inf")

for a in cum_sum[:-1]:
    ans = min(ans, abs(2 * a - b))

print(ans)


### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
b = sum(A)

ans = float("inf")
cum_sum = 0

for a in A[:-1]:
    cum_sum += a
    ans = min(ans, abs(2 * cum_sum - b))

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

n,m = map(int,input().split())
a = [0] * m
for i in range(m):
    a[i] = int(input())
 
MOD = 10 ** 9 + 7
dp = [0] * (n + 1)
dp[0] = 1
 
for i in range(1, n + 1):
    if i in a:
        continue
    x = dp[i - 1]
    if i > 1:
        x += dp[i - 2]
    dp[i] = x % MOD
ans = dp[n]
print(ans)

### FIXED CODE ###

N, M = [int(x) for x in input().split()]
a = set(int(input()) for _ in range(M))
 
MOD = 10 ** 9 + 7
dp = [0] * (N + 1)
dp[0] = 1
 
for i in range(1, N + 1):
  if i in a:
    continue
  x = dp[i - 1]
  if i > 1:
    x += dp[i - 2]
  dp[i] = x % MOD
 
ans = dp[N]
print(ans)
### BUGGY CODE ###

N,M = map(int,input().split())
onelist,nlist = [],[]
for i in range(M):
    aa,bb = map(int,input().split())
    if aa == 1:
        onelist.append(bb)
    if bb == N:
        nlist.append(aa)

for b in onelist:
    if b in nlist:
        print("POSSIBLE")
        exit()

print("IMPOSSIBLE")


### FIXED CODE ###

N,M = map(int,input().split())
onelist,nlist = [],[]
for i in range(M):
    aa,bb = map(int,input().split())
    if aa == 1:
        onelist.append(bb)
    if bb == N:
        nlist.append(aa)


if len(set(onelist) & set(nlist)) == 0:
    print("IMPOSSIBLE")
else:
    print("POSSIBLE")
### BUGGY CODE ###

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

count = N
for i in range(N):
    count = min(count, S[:i].count('W') + S[i+1:].count('E'))
print(count)


### FIXED CODE ###

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

count = S[1:].count('E')
ans = count
for i in range(1, N):
    if S[i] == 'E':
        count -= 1
    if S[i-1] == 'W':
        count += 1
    ans = min(ans, count)
print(ans)
### BUGGY CODE ###

#C_Snuke Festival
import bisect

def SnukeFestival(N, A, B, C):
    A = sorted(A)
    B = sorted(B)
    C = sorted(C)
    count = 0
    for a in A:
        start = bisect.bisect_right(B, a)
        for j in range(start, N):
            b = B[j]
            count += (N-bisect.bisect_right(C, b))
    print(count)

if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    C = list(map(int, input().split()))
    SnukeFestival(N, A, B, C)

### FIXED CODE ###

#C_Snuke Festival
import bisect

def SnukeFestival(N, A, B, C):
    A = sorted(A)
    B = sorted(B)
    C = sorted(C)
    count = 0

    for b in B:
        n_a = bisect.bisect_left(A,b)
        n_c = bisect.bisect_right(C,b)
        count += n_a * (N - n_c)

    print(count)

if __name__ == "__main__":
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    C = list(map(int, input().split()))
    SnukeFestival(N, A, B, C)
### BUGGY CODE ###

def len_lcs(s1, s2):
    """Find length of the longest common sequence(LCS) of strings s1 and s2.

    >>> len_lcs("abc", "abc")
    3
    >>> len_lcs("abcbdaba", "bdcaba")
    5
    """
    def match(c1, c2):
        if c1 == c2:
            return 1
        else:
            return 0

    if len(s1) == 0 or len(s2) == 0:
        return 0

    primary = [0] * len(s1)
    secondary = [0] * len(s1)

    for i in range(len(s2)):
        for j in range(len(s1)):
            if j == 0:
                secondary[j] = max(primary[j], match(s1[j], s2[i]))
            else:
                secondary[j] = max(secondary[j-1], primary[j],
                                   primary[j-1] + match(s1[j], s2[i]))

        primary, secondary = secondary, primary

    return primary[len(s1)-1]


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

    for _ in range(n):
        s1 = input()
        s2 = input()
        print(len_lcs(s1, s2))


if __name__ == '__main__':
    run()



### FIXED CODE ###

import sys


def len_lcs(s1, s2):
    """Find length of the longest common sequence(LCS) of strings s1 and s2.
    The complexity is ~MN.

    >>> len_lcs("abc", "abc")
    3
    >>> len_lcs("abcbdaba", "bdcaba")
    5
    """
    results = [0] * len(s1)

    for i, c2 in enumerate(s2):
        sec1, pr1 = 0, 0
        for j, c1 in enumerate(s1):
            pr2 = results[j]
            if c1 == c2:
                mval = pr1 + 1
            elif sec1 > pr2:
                mval = sec1
            else:
                mval = pr2

            results[j] = mval
            sec1, pr1 = mval, pr2

    return results[-1]


def run():
    n = int(input())
    s = []
    for line in sys.stdin:
        s.append(line.strip())
    for i in range(0, 2*n, 2):
        print(len_lcs(s[i], s[i+1]))

run()
### BUGGY CODE ###

def main():
    N = int(input())
    S = list(str(input()))
    print()
    sum = 0
    for i in range(0, N-2):
        si = S[i]
        for j in range(i, N-1):
            sj = S[j]
            for k in range(j, N):
                sk = S[k]
                #if S[i] != S[j] and S[i] != S[k] and S[j] != S[k]:
                if si != sj and si != sk and sj != sk:
                    if j - i != k -j:
                        sum += 1
    print(sum)



main()

### FIXED CODE ###

def main():
    N = int(input())
    S = list(str(input()))
    sum = S.count("R") * S.count("G") * S.count("B")
    for i in range(0, N-2):
        si = S[i]
        for j in range(i+1, N-1):
            sj = S[j]
            k = 2*j -i  # Nを超える
            if k < N:
                sk = S[k]
                #if j - i != k -j and si != sj and si != sk and sj != sk:
                if si != sj and si != sk and sj != sk:
                    sum -= 1
    print(sum)

    # 提出 #11871188


main()
### BUGGY CODE ###

import math

n = int(input())

for i in range(1, n+1):
    ans = 0
    for j in range(1, int(math.sqrt(i))):
        for k in range(1, int(math.sqrt(i))):
            if i-(3*((j**2)+(k**2))/4)-((j*k)/2) > 0:
                z = math.sqrt(i-(3*((j**2)+(k**2))/4)-((j*k)/2))-((j+k)/2)
                if z-int(z) == 0 and z > 0:
                    ans += 1
    print(ans)


### FIXED CODE ###

import math

n = int(input())
ans_list = [0 for i in range(n+1)]

for i in range(1,101):
    for j in range(1, 101):
        for k in range(1, 101):
            temp = i*i + j*j + k*k + i*j + j*k + k*i
            if temp <= n:
                ans_list[temp] += 1

for i in range(1, n+1):
    print(ans_list[i])
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from itertools import combinations_with_replacement 
from collections import defaultdict
from operator import itemgetter
def main():
    s = readline().rstrip().decode()
    K = int(readline())
    N = len(s)
    p = [int(i) for i in range(N)]
    S = set()
    for pair in combinations_with_replacement(p, 2):
        l, r = pair
        S.add(s[l:r+1])
    lis = []
    for sub in S:
        lis.append(sub)
    lis.sort()
    print(lis[K-1])
if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(1000000)

def main():
    s = readline().rstrip().decode()
    K = int(readline())
    #sに含まれる文字を一文字ずつ抽出する.
    #ここで抽出した文字を組み合わせて辞書順に文字列を構成していく
    #K<=5だから高々26^5個の文字列を構成することになる
    l = sorted(list(set(s)))
    #cnd:=構成した文字列を辞書順に格納するリスト
    cnd = []
    #f(sub):=subから構成可能なK文字以下のSの部分文字列を構成する関数
    def f(sub):
        cnd.append(sub)
        if len(sub) < K: 
            #lから選んでsubに一文字追加する
            for i in l:
                nx = sub+i
                if nx in s:
                    f(nx)
    for i in l:
        f(i) 
    print(cnd[K-1])
if __name__ == '__main__':
    main()