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

import itertools
from collections import deque
from sys import stdin
input = stdin.readline


def main():
  H, W = list(map(int, input().split()))

  M = [input()[:-1] for _ in range(H)]

  def bfs(start, goal):
    dist = [[float('inf')]*W for _ in range(H)]
    dist[start[0]][start[1]] = 0
    # is_visited = set()
    is_visited = [[0]*W for _ in range(H)]
    q = deque([start])
    while len(q):
      now_h, now_w = q.popleft()
      if M[now_h][now_w] == '#':
        return
      # is_visited.add((now_h, now_w))
      is_visited[now_h][now_w] = 1
      for next_h, next_w in ((now_h+1, now_w),
                             (now_h-1, now_w),
                             (now_h, now_w-1),
                             (now_h, now_w+1)):

        # if ((next_h, next_w) in is_visited) or not(0 <= next_h < H) or not(0 <= next_w < W):
        if not(0 <= next_h < H) or not(0 <= next_w < W) or \
           is_visited[next_h][next_w] or \
           M[next_h][next_w] == '#':
          continue

        dist[next_h][next_w] = dist[now_h][now_w] + 1
        if goal == (next_h, next_w):
          return dist[next_h][next_w]
        q.append((next_h, next_w))

  all_ = []
  for h in range(H):
    for w in range(W):
      all_.append((h, w))

  max_ = 0
  for start, goal in itertools.combinations(all_, 2):
    if M[start[0]][start[1]] == '.' and M[goal[0]][goal[1]] == '.':
      max_ = max(max_, bfs(start, goal))

  print(max_)


if(__name__ == '__main__'):
  main()


### FIXED CODE ###

import itertools
from collections import deque
from sys import stdin
input = stdin.readline


def main():
  H, W = list(map(int, input().split()))

  M = [input()[:-1] for _ in range(H)]

  def bfs(start):
    dist = [[float('inf')]*W for _ in range(H)]
    dist[start[0]][start[1]] = 0

    q = deque([start])
    max_ = 0

    while len(q):
      now_h, now_w = q.popleft()
      for next_h, next_w in ((now_h+1, now_w),
                             (now_h-1, now_w),
                             (now_h, now_w-1),
                             (now_h, now_w+1)):

        if not(0 <= next_h < H) or not(0 <= next_w < W) or \
           (dist[next_h][next_w] != float('inf')) or \
           M[next_h][next_w] == '#':
          continue

        temp = dist[now_h][now_w] + 1
        dist[next_h][next_w] = temp
        if max_ < temp:
          max_ = temp
        q.append((next_h, next_w))
    return max_

  max_ = 0
  for h in range(H):
    for w in range(W):
      if M[h][w] == '.':
        max_ = max(bfs((h, w)), max_)

  print(max_)


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

import sys
stdin = sys.stdin
import math
from operator import mul
from functools import reduce

mod = 10**9 + 7

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

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

n, a, b = na()
ans = 2**n - 1 - cmb(n, a) - cmb(n, b)
print(ans % mod)

### FIXED CODE ###

import sys
stdin = sys.stdin
from math import factorial

mod = 10**9 + 7

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

n, a, b = na()

def pow(a,n,p=mod):
    bi=str(format(n,"b"))
    res=1
    for i in range(len(bi)):
        res=(res*res) %p
        if bi[i]=="1":
            res=(res*a) %p
    return res
def comb(a, b, p=mod):
    res = 1
    pres = 1
    for i in range(b):
        res = (res*(a-i))%p
        pres = (pres*(i+1))%p
    return res*pow(pres, p-2, p) % p
print((pow(2, n) - 1 - comb(n, a) - comb(n, b))%mod)
### BUGGY CODE ###

N, X, Y = map(int, input().split())
S = [[N]*N for _ in range(N)]

for i in range(N):
    S[i][i] = 0

    if i != N-1:
        S[i][i+1] = 1
        S[i+1][i] = 1

S[X-1][Y-1] = 1
S[Y-1][X-1] = 1

for _ in range(10**3):
    for i in range(N):
        for j in range(N):
            for k in range(N):
                S[i][j] = min(S[i][j], S[i][k]+S[k][j])

#print(S)

dist = [0]*N

from itertools import (
    accumulate,  # 累積和のイテレータ
    groupby,  # 値をkey,同じ値の集まりをgroup
    permutations,  # 順列
    combinations,  # 組み合わせ
    product,  # 重複あり順列（直積, 深いネストにも使える）
)

for i, j in combinations(list(range(N)), 2):
    d = S[i][j]
    dist[d] += 1

#print(dist)

for i in range(1, len(dist)):
    print(dist[i])

### FIXED CODE ###

N, X, Y = map(int, input().split())
S = [list(reversed(list(range(1, i+1)))) + list(range(N-i)) for i in range(N)]

S[X-1][Y-1] = 1
S[Y-1][X-1] = 1

for i in range(N):
    for j in range(N):
        x, y = X-1, Y-1
        S[i][j] = min(S[i][j], S[i][x]+1+S[y][j])

#print(S)

dist = [0]*N

from itertools import (
    accumulate,  # 累積和のイテレータ
    groupby,  # 値をkey,同じ値の集まりをgroup
    permutations,  # 順列
    combinations,  # 組み合わせ
    product,  # 重複あり順列（直積, 深いネストにも使える）
)

for i, j in combinations(list(range(N)), 2):
    d = S[i][j]
    dist[d] += 1

#print(dist)

for i in range(1, len(dist)):
    print(dist[i])
### BUGGY CODE ###

import math

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

now_max = 1

for i in range(int(math.pow(P, 1 / N)) + 1, 0, -1):
    if P % (i ** N) == 0:
        now_max = i
        break

print(now_max)

### FIXED CODE ###

n, p = map(int, input().split())
if n == 1:
    print(p)
else:
    for i in range(1, round(p**(1/n))+1):
        if p % i**n ==0:
            res = i
    print(res)
### BUGGY CODE ###

from collections import deque
N, Q = map(int, input().split())
root = [[] for i in range(N)]
ans = [0]*N

for i in range(N-1):
  a, b = map(int, input().split())
  root[a-1].append(b)
  
for i in range(Q):
  p, x = map(int, input().split())
  ans[p-1] += x
  
now = 1
visit = deque([1])
while len(visit) < N:
  if root[now-1] == []:
    now = visit[visit.index(now)-1]
  else:
    go = root[now-1][0]
    root[now-1].pop(0)
    visit.append(go)
    ans[go-1] += ans[now-1]
    now = go
    
print(' '.join(map(str, ans)))

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)
inf = 10**17
mod = 10**9+7


n, q = map(int, input().split())
g = [[] for _ in range(n)]
val = [0] * n

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

for _ in range(q):
    p, x = map(int, input().split())
    val[p - 1] += x

seen = [False] * n
def dfs(v):
    seen[v] = True
    for nv in g[v]:
        if seen[nv]:
            continue
        val[nv] += val[v]
        dfs(nv)

dfs(0)
print(*val)
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
import math
import sys

def atkin(limit):
    sqrt_limit = int(math.sqrt(limit))
    is_prime = [False] * (limit + 1)
    primes = []
    if limit == 1:
        return primes
    if limit >= 2:
        is_prime[2] = True
    if limit >= 3:
        is_prime[3] = True
    for x in range(1, sqrt_limit):
        for y in range(1, sqrt_limit):
            k = 4*x**2 + y**2
            if k <= limit and (k%12 == 1 or k%12 == 5):
                is_prime[k] ^= True
            k = 3*x**2 + y**2
            if k <= limit and k%12 == 7:
                is_prime[k] ^= True
            k = 3*x**2 - y**2
            if x > y and k <= limit and k%12 == 11:
                is_prime[k] ^= True

    r = 5
    while r**2 < limit:
        if is_prime[r]:
            i = r**2
            while i < limit:
                is_prime[i] = False
                i += r**2
        r += 1

    for i in range(limit + 1):
        if is_prime[i]:
            primes.append(i)

    return primes

for line in sys.stdin.readlines():
    n = int(line.strip())
    primes = atkin(n)
    #print(primes)
    print(len(primes))

### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-
import sys

LIMIT = 1000000
is_prime = [True] * (LIMIT+1)
p = 2
while p**2 <= LIMIT:
    if is_prime[p]:
        for i in range(p*2, LIMIT+1, p):
            is_prime[i] = False
    p += 1

for line in sys.stdin.readlines():
    n = int(line.strip())
    if n <= 1:
        print(0)
        continue
    if n == 2:
        print(1)
        continue
    num_prime = 1
    for i in range(3, n+1):
        if is_prime[i]:
            num_prime += 1
    print(num_prime)
### BUGGY CODE ###

r1,c1,r2,c2=map(int,input().split())
mod=10**9+7
f=[1]
for i in range(2*10**6+7):f+=[f[-1]*(i+1)%mod]
ans=0
for i in range(c1,c2+1):
  d=(r2+1)*f[i+r2+1]*f[r1]
  d%=mod
  d=(d+(mod-r1*f[r2+1]*f[i+r1]))%mod
  d*=pow((i+1)*f[i]*f[r1]*f[r2+1],mod-2,mod)
  d%=mod
  ans+=d
  ans%=mod
print(ans)

### FIXED CODE ###

r1,c1,r2,c2=map(int,input().split())
mod=10**9+7
f=[1]
for i in range(2*10**6+7):f+=[f[-1]*(i+1)%mod]
ans=0
for i in range(c1,c2+1):
  d=((r2+1)*f[i+r2+1]%mod)*f[r1]
  d%=mod
  d=(d+(mod-((r1*f[r2+1]%mod)*f[i+r1])%mod))%mod
  d*=pow((((i+1)*f[i]%mod)*f[r1]%mod)*f[r2+1]%mod,mod-2,mod)
  d%=mod
  ans+=d
  ans%=mod
print(ans)
### BUGGY CODE ###

import pprint
N=int(input())
l2=[]
bit2=50
bit5=22
#table=[[0 for _ in range(20)] for _ in range(15)]
#table=[[0 for _ in range(45)] for _ in range(20)]
table=[[0 for _ in range(bit2)] for _ in range(bit5)]
from decimal import *
getcontext().prec=28
for i in range(N):
    pf={}
    n=float(input())
    #print(n)
    n=n*pow(10,9)
    count2=0
    count5=0
    n=Decimal(n)
    #print(n,kake)
    while n/2==n//2:
        n=n//2
        count2=count2+1
    while n/5==n//5:
        n=n//5
        count5=count5+1
    table[count5][count2]=table[count5][count2]+1
    l2.append([count2,count5])
#pprint.pprint(table)
#print(l2)
ans=0
for i in range(bit5):
    for j in range(bit2):
        num=table[i][j]
        min2=max(0,18-j)
        min5=max(0,18-i)
        cnt=0
        if num>0:
            #print(min2,min5,i,j,num)
            for k in range(min5,bit5):
                for l in range(min2,bit2):
                    cnt=cnt+table[k][l]
            if (min2<=j)and(min5<=i):
                cnt=cnt-1
            ans=ans+num*cnt
            #print(ans)
print(ans//2)



### FIXED CODE ###

import pprint
from collections import deque
N=int(input())
l2=[]
bit2=50
bit5=22
#table=[[0 for _ in range(20)] for _ in range(15)]
#table=[[0 for _ in range(45)] for _ in range(20)]
table=[[0 for _ in range(bit2)] for _ in range(bit5)]
for i in range(N):
    n=list(input())
    #print(n)
    cnt=9
    d=deque()
    flag=1
    for i in range(len(n)):
        if n[i]==".":
            flag=0
        else:
            d.append(n[i])
            if flag==0:
                cnt=cnt-1
    for i in range(cnt):
        d.append("0")
    n=int("".join(d))
    #print(n)
    count2=0
    count5=0
    #print(n,kake)
    while n%2==0:
        n=n//2
        count2=count2+1
    while n%5==0:
        n=n//5
        count5=count5+1
    table[count5][count2]=table[count5][count2]+1
    l2.append([count2,count5])
#pprint.pprint(table)
#print(l2)
ans=0
for i in range(bit5):
    for j in range(bit2):
        num=table[i][j]
        min2=max(0,18-j)
        min5=max(0,18-i)
        cnt=0
        if num>0:
            #print(min2,min5,i,j,num)
            for k in range(min5,bit5):
                for l in range(min2,bit2):
                    cnt=cnt+table[k][l]
            if (min2<=j)and(min5<=i):
                cnt=cnt-1
            ans=ans+num*cnt
            #print(ans)
print(ans//2)
### BUGGY CODE ###

class DoublyLinkedList:
    def __init__(self):
        self.nil = self.make_node(None)
        self.nil['next'] = self.nil
        self.nil['prev'] = self.nil

    def make_node(self,v):
        return {'key':v, 'next':None, 'prev':None}

    def __str__(self):
        ret = ''
        n = self.nil['next']
        while True:
            if n['key'] == None:
                break
            else:
                ret += str(n['key']) + ' '
                n = n['next']
        return ret[:-1]


    def insert(self,v):
        n = self.make_node(v)
        n['next'] = self.nil['next']
        self.nil['next']['prev'] = n
        n['prev'] = self.nil
        self.nil['next'] = n

    def delete(self,v):
        self.delete_node(self.list_search(v))

    def delete_node(self,n):
        if n['key'] == None: return
        n['next']['prev'] = n['prev']
        n['prev']['next'] = n['next']

    def list_search(self,v):
        cur = self.nil['next']
        while (cur['key'] != None) and (cur['key'] != v):
            cur = cur['next']
        return cur

    def deleteFirst(self):
        self.delete_node(self.nil['next'])

    def deleteLast(self):
        self.delete_node(self.nil['prev'])

n = int(raw_input())

l = DoublyLinkedList()
for i in range(n):
    c = raw_input()
    if c == "deleteFirst":
        l.deleteFirst()
    elif c == "deleteLast":
        l.deleteLast()
    else:
        op,val = c.split(' ')
        val = int(val)
        if op == "insert":
            l.insert(val)
        elif op == "delete":
            l.delete(val)

print l

### FIXED CODE ###

class DoublyLinkedList:
    def __init__(self):
        self.nil = self.make_node(None)
        self.nil['next'] = self.nil
        self.nil['prev'] = self.nil

    def make_node(self,v):
        return {'key':v, 'next':None, 'prev':None}

    def dump(self):
        n = self.nil['next']
        while True:
            if n['key'] == None:
                break
            else:
                print str(n['key']),
                n = n['next']
        print


    def insert(self,v):
        n = self.make_node(v)
        n['next'] = self.nil['next']
        self.nil['next']['prev'] = n
        n['prev'] = self.nil
        self.nil['next'] = n

    def delete(self,v):
        self.delete_node(self.list_search(v))

    def delete_node(self,n):
        if n['key'] == None: return
        n['next']['prev'] = n['prev']
        n['prev']['next'] = n['next']

    def list_search(self,v):
        cur = self.nil['next']
        while (cur['key'] != None) and (cur['key'] != v):
            cur = cur['next']
        return cur

    def deleteFirst(self):
        self.delete_node(self.nil['next'])

    def deleteLast(self):
        self.delete_node(self.nil['prev'])

n = int(raw_input())
commands = []
for i in range(n):
    commands.append(raw_input())

l = DoublyLinkedList()
for c in commands:
    a = c[6]
    if a == "F":
        l.deleteFirst()
    elif a == "L":
        l.deleteLast()
    else:
        val = int(c[7:])
        op = c[0]
        if op == "i":
            l.insert(val)
        else:
            l.delete(val)

l.dump()
### BUGGY CODE ###

n, q = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(n-1)]
ab.sort()
p = [0]*n
for i in range(q):
  a, b = map(int, input().split())
  p[a - 1] += b
s = ""
for i in ab:
  p[i[1]-1] += p[i[0]-1]
print(" ".join(map(str, p)))

### FIXED CODE ###

n, q = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(n-1)]
ab.sort()
p = [0]*n
for i in range(q):
  a, b = map(int, input().split())
  p[a - 1] += b
s = ""
for i in ab:
  p[i[1]-1] += p[i[0]-1]
print(*p)
### BUGGY CODE ###

n = int(input())
a = [ int(x) for x in input().split() ]
counter = 0

for i in range(n-1):
    if counter == n:
        print(0)
    else:
        t = a.count(i+1)
        counter = counter + t
        print(t)

print(0)


### FIXED CODE ###

n = int(input())
a = [ int(x) for x in input().split() ]
ans = [0] * n

for i in range(n-1):
    ans[a[i]] += 1

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

print(0)
### BUGGY CODE ###

N, X = map(int, input().split())
x = list(map(lambda x:abs(int(x)-X), input().split()))

#for i in range(N):
#	x[i] = abs(x[i] - X)

x.sort()
#x.reverse()

xmin = x[0]
#xmin = x[N-1]
'''
div = []
for i in range(int(xmin/2)+1, 0, -1):
	if xmin % i == 0:
		div.append(i)

for d in div:
	for xi in x:
		if xi % d != 0:
			break
	else:
		D = d
		break

print(D)
'''
for d in range(xmin,0,-1):
	for xi in x:
		if xi % d != 0:
			break
	else:
		D = d
		break

print(D)

### FIXED CODE ###

N, X = map(int, input().split())
x = list(map(lambda x:abs(int(x)-X), input().split()))

#for i in range(N):
#	x[i] = abs(x[i] - X)

x.sort()
#x.reverse()

xmin = x[0]
#xmin = x[N-1]
'''
div = []
for i in range(int(xmin/2)+1, 0, -1):
	if xmin % i == 0:
		div.append(i)

for d in div:
	for xi in x:
		if xi % d != 0:
			break
	else:
		D = d
		break

print(D)
'''
for d in range(xmin,0,-1):
	for xi in x:
		if xi % d != 0:
			break
	else:
		D = d
		break

print(D)
### BUGGY CODE ###

import heapq

n, m = [int(v) for v in input().split(' ')]

costs = []
links = []
for i in range(n):
    costs.append([-1] * i)
    links.append([])

for i in range(m):
    l, r, c = [int(v) for v in input().split(' ')]
    l -= 1
    r -= 1
    links[r].append((l, c))

h = []
heapq.heappush(h, (0, n-1))
closed = 0
while len(h) > 0:
    c0, n0 = heapq.heappop(h)
    closed |= (1 << n0)
    if n0 == 0:
        print(c0)
        exit()

    for n1, c1 in links[n0]:
        if (closed & (1 << n1)) != 0:
            continue
        heapq.heappush(h, (c0 + c1, n1))

    for n1 in range(n0 + 1, n):
        if (closed & (1 << n1)) != 0:
            break
        heapq.heappush(h, (c0, n1))

print("-1")

### FIXED CODE ###

import heapq

n, m = [int(v) for v in input().split(' ')]

links = []
for i in range(n):
    links.append([])

for i in range(m):
    l, r, c = [int(v) for v in input().split(' ')]
    l -= 1
    r -= 1
    links[r].append((l, c))

h = []
heapq.heappush(h, (0, n-1))
closed = 0
while len(h) > 0:
    c0, n0 = heapq.heappop(h)
    if (closed & (1 << n0)) != 0:
        continue
    closed |= (1 << n0)
    if n0 == 0:
        print(c0)
        exit()

    for n1, c1 in links[n0]:
        if (closed & (1 << n1)) != 0:
            continue
        heapq.heappush(h, (c0 + c1, n1))

    n2 = n0 + 1
    if n2 < n:
        if (closed & (1 << n2)) == 0:
            heapq.heappush(h, (c0, n2))

print("-1")
### BUGGY CODE ###

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

result = []
for a in range(N+1):
  for b in range(N+1):
    c = N - a - b
    for c in range(c+1):
      total = a * 10000 + b * 5000 + c * 1000
      if (total == Y) and (a + b + c == N):
        result.append([a, b, c])

if len(result) == 0:
  print("-1 -1 -1")
else:
  print(" ".join(map(str, result[0])))

### FIXED CODE ###

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

result = []
for a in range(N+1):
  for b in range(N+1):
    c = max(N - a - b, 0)
    total = a * 10000 + b * 5000 + c * 1000
    if (total == Y) and (a + b + c == N):
      result.append([a, b, c])

if len(result) == 0:
  print("-1 -1 -1")
else:
  print(" ".join(map(str, result[0])))
### BUGGY CODE ###

N,K=map(int,input().split())
A=list(map(int,input().split()))
B=sorted(A)
C=[]
for i in range(N-1):
  for j in range(i+1,N):
    C.append(A[i]*A[j])
print(sorted(C)[K-1])

### FIXED CODE ###

N,K=map(int, input().split())
A=list(map(int, input().split()))
A=sorted(A)
import numpy as np
A=np.array(A,dtype="int64")
Z=A[A==0]
H=A[A<0]
S=A[A>0]
l,r=-10**19,10**19
while r-l>1:
  mid=(r+l)//2
  cnt=0
  cnt+=A.searchsorted(mid//S,side="right").sum()
  cnt+=(N-A.searchsorted((-mid-1)//(-H),side="right")).sum()
  cnt-=np.count_nonzero(A*A<=mid)
  if mid>=0:
    cnt+=len(Z)*N 
  cnt//=2
  if cnt>=K:
    r=mid
  else:
    l=mid 
print(r)
### BUGGY CODE ###

AB = list(map(int, input().split()))
ketaB = 0

tmp = AB[1]
while 1:
    ketaB += 1
    if tmp ==0 or tmp == 1:
        break
    tmp /= 2
tmp = AB[0]

ans = 0
tmp = 2 ** (ketaB)
tmp2 = 0
A = AB[0]
B = AB[1]
check = 0
while tmp != 1:
    A = AB[0]
    B = AB[1]
    tmp2 = 0
    check =0
    while A % tmp < (tmp//2):
        if A == B:
            check = 1
            break
        A+=1
    while A % tmp != 0 and check !=1:
        tmp2 += 1
        if A == B:
            check = 1
            break
        A+=1
    A = AB[0]
    while B % tmp >= (tmp//2) and check !=1:
        B -= 1
        tmp2 += 1
    tmp //= 2
    ans += tmp*(tmp2 % 2)
print(int(ans))

### FIXED CODE ###

AB = list(map(int, input().split()))
soto = AB[0] - 1
B = AB[1]
if soto % 4 == 0:
    tmp1 =soto
elif soto % 4 == 1:
    tmp1 = 1
elif soto % 4 == 2:
    tmp1= soto + 1
else :
    tmp1 = 0

if B % 4 == 0:
    tmp2 =B
elif B % 4 == 1:
    tmp2 = 1
elif B % 4 == 2:
    tmp2= B + 1
else :
    tmp2 = 0

ans = tmp1 ^ tmp2
print(ans)
### BUGGY CODE ###

N = int(input())
S = input()
result = N
for i in range(N):
    r = S[:i].count("W") + S[i+1:].count("E")
    if r < result:
        result = r
print(result)

### FIXED CODE ###

N = int(input())
S = input()
left_w_count = 0
right_e_count = S[1:].count("E")
result = right_e_count
for i in range(1, N):
    if S[i - 1] == "W":
        left_w_count += 1
    if S[i] == "E":
        right_e_count -= 1
    r = left_w_count + right_e_count
    if r < result:
        result = r
print(result)
### BUGGY CODE ###

n, k = map(int, input().split())
if k == 1:
	print(0)
else:
	while True:
		prev = n
		n = abs(n - k)
		if n >= prev:
			break
	print(prev)


### FIXED CODE ###

n, k = map(int, input().split())
p = n // k
print(min(abs(n - p * k), abs(n - (p + 1) * k)))
### BUGGY CODE ###

s = input()
k = int(input())
n = len(s)

c = set()
for i in range(n-1):
    for j in range(i+1, n+1):
        c.add(s[i:j])

if k <= len(c):
    c = list(c)
    c.sort()
    print(c[k-1])
else: print(s)






### FIXED CODE ###

s = input()
k = int(input())
n = len(s)

# print('s',s,'k',k)
c = set()
for i in range(n):
    # print(s[i:i+5])
    t = s[i:i+5]
    for j in range(1,5+1):
        # print(t[:j])
        c.add(t[:j])

c = list(c)
c.sort()
# print(*c,sep='\n')
print(c[k-1])
### BUGGY CODE ###

n = int(input())
S = [input() for i in range(n)]
c = 0
for i in range(n):
  for j in range(n):
    if i < j and sorted(S[i]) == sorted(S[j]):
      c += 1
print(c)

### FIXED CODE ###

n = int(input())
S = [input() for i in range(n)]
for i in range(n):
  S[i] = sorted(S[i])
S = sorted(S)
c = 0
i = 0
while i < n - 1:
  j = i + 1
  while j < n:
    if S[i] == S[j]:
      j += 1
    else:
      break
  c += (j-i) * (j-i-1) // 2
  i = j  
print(c)
### BUGGY CODE ###

from sys import stdin
from collections import defaultdict 
# from bisect import *
# from heapq import *
# import math
# mod = 10**9+7

H, W, M = map(int, input().split())
raw = defaultdict(int)
col = defaultdict(int)
hw = set()
for i in range(M):
    h, w = map(int, stdin.readline().split())
    raw[h] += 1
    col[w] += 1
    hw.add((h, w))
rawkey = raw.keys()
colkey = col.keys()
ans = 0
for h in rawkey:
    for w in colkey:
        tmp = raw[h] + col[w]
        if (h, w) in hw:
            tmp -= 1
        ans = max(ans, tmp)
print(ans)

### FIXED CODE ###

from sys import stdin
from collections import defaultdict 
# from bisect import *
# from heapq import *
# import math
# mod = 10**9+7

H, W, M = map(int, input().split())
raw = defaultdict(int)
col = defaultdict(int)
hw = set()
for i in range(M):
    h, w = map(int, stdin.readline().split())
    raw[h] += 1
    col[w] += 1
    hw.add((h, w))
mh = max(raw.values())
mw = max(col.values())
rawkey = [h for h in raw.keys() if raw[h] == mh]
colkey = [w for w in col.keys() if col[w] == mw]
for h in rawkey:
    for w in colkey:
        if (h, w) not in hw:
            print(mh + mw)
            exit()
print(mh + mw -1)
### BUGGY CODE ###

n = int( input() )
l = list( map( int, input().split() ) )
 
l = sorted( l )
cnt = 0
for i in range( n ):
  for j in range( i + 1, n ):
    for k in range( j + 1, n ):
      if l[ i ] + l[ j ] <= l[ k ]:
        break
      else:
        cnt += 1

print( cnt )

### FIXED CODE ###

import bisect
n = int( input() )
l = sorted( list( map( int, input().split() ) ))

cnt = 0
for i in range( n ):
  for j in range( i + 1, n ):
    cnt += bisect.bisect_left( l, l[ i ] + l[ j ] ) - ( j + 1 )
    
print( cnt )
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
for i in range(n):
  print(a.count(i+1))

### FIXED CODE ###

n=int(input())
result=[0]*n
a=list(map(int,input().split()))
for i in range(n-1):
  result[a[i]-1]+=1
for j in range (n):
  print(result[j])