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

from collections import deque
h, w = map(int, input().split())
a = []
for i in range(h):
    a.append(str(input()))
que = deque()
allque = deque()

for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            que.append((i, j))
            allque.append((i, j))

dd = ((0, -1), (-1, 0), (0, 1), (1, 0))
ans = 0
d = 0
tmpque = deque()

while que:
    while que:
        y, x = que.popleft() #幅優先探索
        for dx, dy in dd:
            nx = x + dx; ny = y + dy
            if 0 <= nx < w and 0 <= ny < h and (ny, nx) not in allque:
                tmpque.append((ny, nx))
                allque.append((ny, nx))
    que += tmpque
    allque = deque(set(allque))
    que = deque(set(que))
    tmpque = deque()
    if que:
        ans += 1
print(ans)

### FIXED CODE ###

from collections import deque
h, w = map(int, input().split())
a = []
for i in range(h):
    a.append(str(input()))
que = deque()
dist = [[-1]*w for i in range(h)]

for i in range(h):
    for j in range(w):
        if a[i][j] == "#":
            dist[i][j] = 0
            que.append((i, j))


dd = ((0, -1), (-1, 0), (0, 1), (1, 0))
ans = 0
d = 0
while que:
    y, x = que.popleft() #幅優先探索
    d = dist[y][x]
    for dx, dy in dd:
        nx = x + dx; ny = y + dy
        if 0 <= nx < w and 0 <= ny < h and dist[ny][nx] == -1:
            dist[ny][nx] = 0
            que.append((ny, nx))
            dist[ny][nx] = d + 1
print(d)
### BUGGY CODE ###

def make_divisors(n):
    lower_divisors, upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]


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

    dp = [0] * (n+1)
    dp[0] = 0
    dp[1] = 0
    for i in range(2, n+1):
        divisor = make_divisors(i-1)
        dp[i] = dp[i-1] + len(divisor)

    print(dp[-1])


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n = int(input())
    ans = 0
    for a in range(1, n):
        ans += (n-1) // a
    print(ans)

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

A, B, C, D = map(int, input().split())

count = 0
for i in range(A,B+1):
  #print("///////////")
  #print(i)
  if(i % C == 0 and i % D != 0): # 3で割り切れるが５で割り切れない
    #print("2で割り切れるが3で割り切れない")
    pass
  elif(i % D == 0 and i % C != 0): # 5で割り切れるが3で割り切れない
    #print("2で割り切れるが3で割り切れない")
    pass
  elif(i % C == 0 and i % D == 0): # 3で割り切れ、かつ5で割り切れる
    #print("2で割り切れるが3で割り切れる")
    pass
  else:
    #print("どれにもあてはまらない",i)
    count = count + 1
print(count)


### FIXED CODE ###

import fractions
def lcm(a,b):
  return a*b //fractions.gcd(a, b)

A, B,C,D = map(int, input().split())
 
b_num = B//C + B//D - B//lcm(C, D)
a_num = (A-1)//C + (A-1)//D - (A-1)//lcm(C, D)
print((B-(A-1))-(b_num-a_num))
### BUGGY CODE ###

n = int(input())

a = list(str(n))

ans = 0

for i in range(len(a)-3):
    for j in range(len(a)-3-i):
        k = a[i:i+4+j]
        if len(k)==4 and int(k[0])%2 !=0:
            continue
        elif len(k)==4 and k[0]=="2" and k[1]!= "0":
            continue
        elif int("".join(map(str, k)))%2019 == 0:
            ans = ans + 1

print(ans)

### FIXED CODE ###

s = input()[::-1]
#sは文字列 逆向きにしている
sum_of_digits = 0

cnts = [0] * 2019

cnts[0] = 1

d = 1

for c in s:
    sum_of_digits += int(c) * d
    sum_of_digits %= 2019
    d *= 10         #dを１０倍
    d %= 2019       #dを2019で割る（2019は10と素なので意味はないかも）
    cnts[sum_of_digits] += 1
    #cntは2019個ある　modの値が同じごとに個数を計算して足したもの

ans = 0
    
for cnt in cnts:
    ans += cnt * (cnt - 1) // 2  
                    #cnt conbination 2
                    #mod ごとに m(m − 1)/2
        
#(i, j)が条件をみたすのはTi−1 == Tj (mod2019)のとき
#Ti−1 - Tj == 0 (mod2019) と等価 Ti−1 == Tj (mod2019)

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

# coding: utf8

if __name__ == '__main__':
    """
        (A, B)と(A+1, B+1)の結果は同じになる.
        (0, 0), (0, 1) ... (0, N-1)をチェックすれば良くなる.
    """
    N = int(input())
    rows = []
    for _ in range(N):
        rows.append(input())
    ans = 0
    for n in range(N):
        flag = False
        for i in range(N):
            for j in range(N):
                num = j - n if j - n >= 0 else N + (j - n)
                a = i - n if i - n >= 0 else N + (i - n)
                if rows[i][num] != rows[j][a]:
                    flag = True
                    break
            if flag == True:
                break
        if flag == False:
            ans += 1
    print(ans * N)



### FIXED CODE ###

# coding: utf8

if __name__ == '__main_sample__':
    """
        (A, B)と(A+1, B+1)の結果は同じになる.
        (0, 0), (0, 1) ... (0, N-1)をチェックすれば良くなる.
    """
    N = int(input())
    rows = [input() for _ in range(N)]
    ans = 0
    for n in range(N):
        flag = False
        for i in range(N):
            for j in range(N):
                num = j - n if j - n >= 0 else N + (j - n)
                a = i - n if i - n >= 0 else N + (i - n)
                if rows[i][num] != rows[j][a]:
                    flag = True
                    break
            if flag == True:
                break
        if flag == False:
            ans += 1
    print(ans * N)

if __name__ == '__main__':
    """
        高速化された開放
    """
    N = int(input())
    Sss = [input() for _ in range(N)]
    Sss_tr = list(map(''.join, zip(*Sss))) # 転置
    ans = 0
    for k in range(N):
        for i in range(N):
            if (Sss[i][-k:] + Sss[i][:-k]) != Sss_tr[i - k]:
                break
        else:
            ans += N
    
    print(ans)
### BUGGY CODE ###

mod = 10 ** 9 + 7
N = int(input())
A = list(map(lambda x: int(x) % mod, input().split(" ")))

ans = sum((A[i] * A[j]) % mod for i in range(0,N-1) for j in range(i+1,N))

print(ans % mod)


### FIXED CODE ###

mod = 1000000007
N = int(input())
A = list(map(lambda x: int(x) % mod, input().split(" ")))

"""
累積話を計算しておく: O(N)
"""
_sum = 0
for i in range(N):
    _sum += A[i]
    _sum %= mod

"""
1重ループ内で下記を行う: O(N)

- 端のブロックを累積和から崩す（減算）
- 端のブロックと累積和をかける
- modをとる
"""
ans = 0
for i in range(N):
    # 累積和の端のブロックを崩す
    _sum -= A[i]

    ans += A[i] * _sum
    ans %= mod

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

def prog(x):
    n = len(x)
    y = [int(i * 10**9) for i in x]
    #y

    def count25(n):
        two = five = 0
        while n % 2 == 0:
            two += 1
            n //= 2
        while n % 5 == 0:
            five += 1
            n //= 5
        return two, five

    two = [0] * n
    five = [0] * n
    for i in range(n):
        two[i], five[i] = count25(y[i])
    count = 0
    for i in range(n - 1):
        for j in range(i + 1, n):
            #if min(two[i] + two[j], five[i] + five[j]) >= 18:
            if two[i] + two[j] >= 18 and five[i] + five[j] >= 18:
                #print(min(two1,two2) + min(five1, five2), two1, two2, five1, five2)
                #print(y[i] * y[j], (y[i] * y[j]) / 10**18)
                #print(y[i] / 10**9, y[j] / 10**9)
                #print('=================')
                count += 1
    print(count)

n = int(input())
x = [0] * n
x = [float(input()) for i in range(n)]
prog(x)


### FIXED CODE ###

def conv(s):
    if s.find('.') == -1:
        s += '.'
    s = s.rstrip('0')
    t = len(s) - s.find('.') - 1
    a = int(s.replace('.', ''))
    if a == 0:
        return (0, 0)
    x, y = -t, -t
    while a % 5 == 0:
        x += 1
        a //= 5
    while a % 2 == 0:
        y += 1
        a //= 2
    return (x, y)


N, *A = open(0).read().split()
N = int(N)

d = {}
for a in A:
    t = conv(a)
    d.setdefault(t, 0)
    d[t] += 1

result = 0
xs = list(d.keys())
for i in range(len(xs)):
    x, y = xs[i]
    t = d[xs[i]]
    if x >= 0 and y >= 0:
        result += t * (t - 1) // 2
    for j in range(i + 1, len(xs)):
        m, n = xs[j]
        if x + m >= 0 and y + n >= 0:
            result += t * d[xs[j]]
print(result)
### BUGGY CODE ###

n = int(input())
cnt = 0
for i in range(1, n+1):
    if set(str(i)) == set(['7', '5', '3']):
        cnt += 1
print(cnt)

### FIXED CODE ###

n = int(input())
def dfs(s):
  if int(s) > n:
    return 0
  ret = 1 if all([s.count(c) > 0 for c in '753']) else 0
  for c in '753':
    ret += dfs(s+c)
  return ret
print(dfs('0'))
### BUGGY CODE ###

 
N, M = map(int, input().split())
mod = 1000000007
dp = [0] * (N+1)
A = [int(input()) for _ in range(M)] 
if (N-1 in A) == False:
    dp[N], dp[N-1] = 1, 1
else:
    dp[N] = 1

for i in range(N-2, -1, -1):
    if (i in A) == False:
        dp[i] = dp[i + 1] + dp[i + 2] 

print(dp[0] % mod)

### FIXED CODE ###

N, M = map(int, input().split())
mod = 1000000007
dp = [0] * (N+2)
A = set([int(input()) for _ in range(M)]) 
dp[-2] = 1

for i in range(N-1, -1, -1):
    if (i in A) == False:
        dp[i] = (dp[i + 1] + dp[i + 2]) % mod 

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

from sys import stdin
input = stdin.readline

from collections import deque

X = int(input())
s = {}
q = deque()

q.append([1, 0])
while True:
	ab = q.popleft()
	tmp = ab[0] ** 5 - ab[1] ** 5
	if (tmp == X):
		print(ab[0], ab[1])
		quit()
	elif (tmp > X):
		q.append([ab[0] - 1, ab[1]])
		q.append([ab[0], ab[1] - 1])
	else:
		q.append([ab[0] + 1, ab[1]])
		q.append([ab[0], ab[1] - 1])


### FIXED CODE ###

from sys import stdin
input = stdin.readline

from collections import deque

X = int(input())
s = {}
q = deque()
q.append((1, 0))
done = {(1, 0)}

while True:
	ab = q.popleft()
	tx = ab[0] ** 5 - ab[1] ** 5
	#print(ab)
	if (tx == X):
		print(ab[0], ab[1])
		quit()
	elif (tx > X):
		if ((ab[0] - 1, ab[1]) not in done):
			q.append((ab[0] - 1, ab[1]))
			done.add((ab[0] - 1, ab[1]))
		if (ab[1] > 0 or (ab[0], ab[1] + 1) not in done):
			q.append((ab[0], ab[1] + 1))
			done.add((ab[0], ab[1] + 1))
		if (ab[1] <= 0 or (ab[0], ab[1] - 1) not in done):
			q.append((ab[0], ab[1] - 1))
			done.add((ab[0], ab[1] - 1))
	else:
		if ((ab[0] + 1, ab[1]) not in done):
			q.append((ab[0] + 1, ab[1]))
			done.add((ab[0] + 1, ab[1]))
		if (ab[1] <= 0 or (ab[0], ab[1] - 1) not in done):
			q.append((ab[0], ab[1] - 1))
			done.add((ab[0], ab[1] - 1))
### BUGGY CODE ###

n,k=map(int,input().split())
lists=list(map(int,input().split()))
GG=[]
for i in range(len(lists)+1):
    for j in range(i,len(lists)):
        
        G=sum(lists[i:j+1])
        GG.append(G)
        
GG=sorted(GG,reverse=True)      
maxi=format(GG[0],"b")
from collections import deque
d=deque()
e=deque()
for j in range(len(GG)):
    d.append(format(GG[j],"b").zfill(len(maxi)))
answer=0
index=0

while index!=len(maxi):
    counter=0
    for some in d:
        if some[index]=="1":
            counter+=1
            e.append(some)
    if counter>=k:
        answer+=2**(len(maxi)-1-index)
        d=e
        e=deque()
    elif counter<k:
        d=d
        e=deque()
        
    index+=1
    counter=0


print(answer)

### FIXED CODE ###

n,k=map(int,input().split())
lists=list(map(int,input().split()))
GG=[]
sumlist=[0]
a=0
for i in range(len(lists)):
    a+=lists[i]
    sumlist.append(a) 
for i in range(len(sumlist)):
    for j in range(i+1,len(sumlist)):
        
        G=sumlist[j]-sumlist[i]
        GG.append(G)
        
GG=sorted(GG,reverse=True)      
maxi=format(GG[0],"b")
from collections import deque
d=deque()
e=deque()
for j in range(len(GG)):
    d.append(format(GG[j],"b").zfill(len(maxi)))
answer=0
index=0
 
while index!=len(maxi):
    counter=0
    for some in d:
        if some[index]=="1":
            counter+=1
            e.append(some)
    if counter>=k:
        answer+=2**(len(maxi)-1-index)
        d=e
        e=deque()
    elif counter<k:
        d=d
        e=deque()
        
    index+=1
    counter=0
print(answer)
### BUGGY CODE ###

n = int(input())
A = list(map(int, input().split()))
ans = 0
for i in range(n):
    for j in range(i+1, n):
        ans += A[i]*A[j]
ans %= (10**9 + 7)
print(ans)

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
ans = 0
for i in range(n):
    A[i] %= (10**9 +7)
s = sum(A)
for i in range(n-1):
    s -= A[i]
    ans += A[i]*s
print(ans%(10**9 + 7))
### BUGGY CODE ###

from collections import Counter
from math import factorial

def nCk(n, r):
    return factorial(n) // (factorial(n - r) * factorial(r))

n = int(input())
a = list(map(int, input().split()))
b = Counter(a)
c = {}
d = {}
for k, v in b.items():
    c[k] = nCk(v, 2) if v > 1 else 0
    d[k] = nCk(v-1, 2) if v > 2 else 0
total = sum(c.values())
for i in range(n):
    ans = total - c[a[i]] + d[a[i]]
    print(ans)

### FIXED CODE ###

from collections import Counter

def nCk(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

n = int(input())
a = list(map(int, input().split()))
b = Counter(a)
c = {}
d = {}
for k, v in b.items():
    c[k] = nCk(v, 2) if v > 1 else 0
    d[k] = nCk(v-1, 2) if v > 2 else 0
total = sum(c.values())
for i in range(n):
    ans = total - c[a[i]] + d[a[i]]
    print(ans)
### BUGGY CODE ###

N = int(input())
S = []
already = []
ans = 0
for i in range(N):
  temps = input()
  if(temps not in already):
    ans += 1
    already.append(temps)
print(ans)

### FIXED CODE ###

N = int(input())
d = {}
for i in range(N):
  d[input()] = 1
print(len(d))
### BUGGY CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]

for i in range(N):
  except_ls = A[:i] + A[i+1:]
  print(max(except_ls))

### FIXED CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]
B = sorted(A,reverse=True)

for i in range(N):
  if A[i] == B[0]:
    print(B[1])
  else:
    print(B[0])
### BUGGY CODE ###

N,Q=map(int,input().split())
S=str(input())
AC_list=[0]*N
for i in range(1,N):
  if S[i]=='C' and S[i-1]=='A':
    AC_list[i]=1
ans=0
for i in range(Q):
  l,r=map(int,input().split())
  ans=sum(AC_list[l:r])
  print(ans)

### FIXED CODE ###

N,Q=map(int,input().split())
S=str(input())
AC_list=[0]*N
t=0
for i in range(1,N):
  if S[i]=='C' and S[i-1]=='A':
    t+=1
  AC_list[i]=t
ans=0
for i in range(Q):
  l,r=map(int,input().split())
  print(AC_list[r-1]-AC_list[l-1])
### BUGGY CODE ###

n,k = [int(i) for i in input().split()]
p = [int(i) for i in input().split()]
ans = []
chk = 0
for i in range(n-k+1):
  m = sum(p[i:k+i])
  chk = max(chk,m)
  if chk == m:
    ans = [(j+1)/2 for j in p[i:k+i]]
print(sum(ans))

### FIXED CODE ###

def main():  
  import sys
  read = sys.stdin.buffer.read
  readline = sys.stdin.buffer.readline
  readlines = sys.stdin.buffer.readlines
  import numpy as np #pypy不可
  n,k = map(int,readline().split())
  p =  np.array(read().split(),np.int32)
  np.cumsum(p,out=p)
  chk = p[k-1]
  for i in range(n-k):
    c = p[i+k]-p[i]
    chk = max(c,chk)
  print((chk+k)/2)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import collections

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

c = collections.Counter(A)

cnt = 0
if K < len(c.keys()):
    for i in range(1,abs(len(c.keys()) - K)+1):
            cnt += c.most_common()[-i][1]
print(cnt)



### FIXED CODE ###

import collections

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

c = collections.Counter(A)

cnt = 0
most_common = c.most_common()
if K < len(c.keys()):
    for i in range(1,abs(len(c.keys()) - K)+1):
            cnt += most_common[-i][1]
print(cnt)
### BUGGY CODE ###

k,s = map(int,input().split())
cnt = 0
for x in range(0,k+1):
    for y in range(0,k+1):
        for z in range(0,k+1):
            if x+y+z == s:
                cnt += 1
print(cnt)

### FIXED CODE ###

k,s = map(int,input().split())
ans = 0
for x in range(k+1):
    for y in range(k+1):
        if 0 <= s-(x+y) <= k:
            ans += 1
print(ans)
### BUGGY CODE ###

""" AtCoder """

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

A_str = bin(A)
B_str = bin(B)

if len(A_str) == len(B_str):
    ans = 0
    for i in range(A, B + 1):
        ans = ans ^ i
    print(ans)
    exit()

A_max = '0b1'
for _ in range(len(A_str) - 2):
    A_max += '0'
B_min = '0b1'
for _ in range(len(B_str) - 3):
    B_min += '0'
ans = '0b1'
for _ in range(len(B_str) - 3):
    ans += '0'

ans = int(ans, 0)

for i in range(A, int(A_max, 0)):
    ans ^= i
for i in range(int(B_min, 0) + 1, B + 1):
    ans ^= i

print(ans)


### FIXED CODE ###

""" AtCoder """

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

if A % 2 == 0 and B % 2 == 0:
    if (B - A) % 4 == 0:
        tmp = 0
    else:
        tmp = 1
    print(tmp ^ B)
elif A % 2 != 0 and B % 2 == 0:
    if (B - A - 1) % 4 == 0:
        tmp = 0
    else:
        tmp = 1
    print(A ^ tmp ^ B)
elif A % 2 == 0 and B % 2 != 0:
    if (B - A + 1) % 4 == 0:
        tmp = 0
    else:
        tmp = 1
    print(tmp)
else:
    if (B - A) % 4 == 0:
        tmp = 0
    else:
        tmp = 1
    print(A ^ tmp)
### BUGGY CODE ###

n,k=map(int,input().split())
h=list(map(int,input().split()))+[0]*(k+10)
dp=[(float("inf")) for i in range(n+k+10)]
dp[0]=0
def main():
  for i in range(n-1):
    for j in range(k):
      dp[i+j+1]=min(dp[i]+abs(h[i]-h[i+j+1]),dp[i+j+1])
  print(dp[n-1])
main()


### FIXED CODE ###

def main():
  n,k=map(int,input().split())
  h=list(map(int,input().split()))+[0]*(k+10)
  dp=[(float("inf")) for i in range(n+k+10)]
  dp[0]=0
  for i in range(n-1):
    for j in range(k):
      dp[i+j+1]=min(dp[i]+abs(h[i]-h[i+j+1]),dp[i+j+1])
  return (dp[n-1])
print(main())
### BUGGY CODE ###

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

ans=99999999
for b in range(min(A)-N,max(A)+N+1):
    num=0
    for i,a in enumerate(A):
        num += abs(a-(b+i+1))
    if num<ans:ans=num
print(ans)

### FIXED CODE ###

import numpy as np

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

AA=[]
for i,a in enumerate(A):
    AA.append(a-i+1)

b=np.median(AA)
ans=0

for a in AA:
    ans+=abs(a-b)
print(int(ans))
### BUGGY CODE ###

from collections import deque
N = int(input())
dic = {}
for i in range(N):
  a = [int(i) for i in input().split()]
  dic[i+1] = deque(a[:])
count = 0
while True:
  nokori = 0
  flag = True
  log = [-1]*N
  for k in dic.keys():
    k = int(k)
    if dic[k]==deque([]):
      nokori += 1
      continue
    p2 = dic[k][0]
#    print(k,p2)
    if log[p2-1]==1:
      continue
    if dic[p2]==deque([]):
      print(-1)
      break
    if dic[p2][0]==k and log[k-1]==-1 and log[p2-1]==-1:
      a = dic[k].popleft()
      b = dic[p2].popleft()
#      print('%', a,b)
      log[k-1] = 1
      log[p2-1] = 1
      flag = False
      
  if nokori == N:
    print(count)
    break
  count += 1
  if flag:
    print(-1)
    break

### FIXED CODE ###

N = int(input())
es = [[] for i in range(N)]
cand = set()
for i in range(N):
  es[i] = [int(i)-1 for i in input().split()][::-1]
def check(i):
  if es[i]==[]:
    return
  j = es[i][-1]
  if es[j]==[]:
    return
  if es[j][-1]==i:
    cand.add(i)
    cand.add(j)

for i in range(N):
  check(i)
day = 0
while cand:
  day += 1
  precand = cand.copy()
  cand = set()
  for i in precand:
    x = es[i].pop()
  for i in precand:
    check(i)
for i in range(N):
  if len(es[i])!=0:
    print(-1)
    break
else:
  print(day)
### BUGGY CODE ###

n,p = list(map(int,input().split()))
S = input()

if p == 2 or p == 5:
  ans = 0
  for i,s in enumerate(S):
    if int(s)%p == 0:
      ans += i+1
  print(ans)
  exit()

def MS(i,s,pre):
  return (s*i +pre)%p
 
M = [0]*p
pre = 0
ans = 0
i = 1
for s in S[::-1]:
  pre = MS(i,int(s),pre)
  M[pre] += 1
  i *= 10

M[0] += 1
ans = sum(map(lambda m:(m*(m-1))//2, M))
print(ans)


### FIXED CODE ###

n,p = list(map(int,input().split()))
S = input()

if p == 2 or p == 5:
  ans = 0
  for i,s in enumerate(S):
    if int(s)%p == 0:
      ans += i+1
  print(ans)
  exit()

def MS(i,s,pre):
  return (s*i +pre)%p
 
M = [0]*p
M[0] = 1
t = 1
now = 0
for i in S[::-1]:
    i = int(i)
    now += i*t
    now %= p
    M[now] += 1
    t = t*10%p

ans = sum(map(lambda m:(m*(m-1))//2, M))
print(ans)
### BUGGY CODE ###

n,m=map(int,input().split())
a=sorted(list(map(int,input().split())))
l=[list(map(int,input().split())) for i in range(m)]

for b,c in l:
  a+=[c]*b
  a=sorted(a)[b:]

print(sum(a))

### FIXED CODE ###

from sys import stdin
nii=lambda:map(int,stdin.readline().split())

n,m=map(int,input().split())
a=sorted(list(nii()))
l=[list(nii()) for i in range(m)]
l=sorted(l,key=lambda x:x[1],reverse=True)

man=[]
num=0
for b,c in l:
  man+=[c]*b
  num+=b
  if num>n:
    break

ans=0
for i in range(n):
  if i<num:
    ans+=max(a[i],man[i])
  else:
    ans+=a[i]
print(ans)
### BUGGY CODE ###

def main():
    N,W = map(int,input().split())
    w,v = [],[]
    for _ in range(N):
        w_,v_ = map(int,input().split())
        w.append(w_)
        v.append(v_)

    dp = [[0]*(W+1) for _ in range(N+1)]

    for i in range(N):
        for j in range(W+1):
            if j-w[i]<0:
                dp[i+1][j] = dp[i][j]
            else:
                dp[i+1][j] = max(dp[i][j],dp[i][j-w[i]]+v[i])

    print(dp[N][-1])
main()

### FIXED CODE ###

import numpy as np
def main():
    N,W = map(int,input().split())
    w,v = [],[]
    for _ in range(N):
        w_,v_ = map(int,input().split())
        w.append(w_)
        v.append(v_)

    dp = np.zeros((N+1,W+1),dtype=np.int64)
    for i in range(N):
        tmp = np.zeros(W+1,dtype=int)
        tmp[w[i]:] = dp[i][:-w[i]] + v[i]
        dp[i+1] = np.maximum(dp[i],tmp)

    print(dp[N][W])
main()
### BUGGY CODE ###

N=int(input())

def query(i):
    print(i,flush=True)
    s=input()
    if s=='Vacant': exit()
    return s

root=query(0)

def is_ok(ind):
    # 左ならTrue
    response=query(ind)
    if ind%2==1: return root==response:
    else: return root!=response



def bin_search_meguru():
    """
    初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
    まずis_okを定義すべし
    ng, okは,とり得る最小の値-1,とり得る最大の値+1
    """

    # 適当にいじる
    ng = -1  # ind=0が条件を満たすこともあるため
    ok = N  # ind=len(a)-1が条件を満たさないこともあるため

    # いじらない
    # okとngのどちらが大きいかわからないことを考慮
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return False

bin_search_meguru()

### FIXED CODE ###

N = int(input())


def query(i):
    print(i)
    s = input()
    if s == 'Vacant':
        exit()
    return s


root = query(0)


def is_ok(ind):
    # 左ならTrue
    response = query(ind)
    if ind % 2 == 1:
        return root == response
    else:
        return root != response


def bin_search_meguru():
    """
    初期値のng,okを受け取り,is_okを満たす最小(最大)のokを返す
    まずis_okを定義すべし
    ng, okは,とり得る最小の値-1,とり得る最大の値+1
    """

    # 適当にいじる
    ng = -1  # ind=0が条件を満たすこともあるため
    ok = N  # ind=len(a)-1が条件を満たさないこともあるため

    # いじらない
    # okとngのどちらが大きいかわからないことを考慮
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return False


bin_search_meguru()
### BUGGY CODE ###

s = input()
k = int(input())

x = sorted(set(s))

subs_list = []
for i in range(len(s)):
    for j in range(i+1, len(s)+1):
        subs_list.append(s[i:j])

ans = sorted(set(subs_list))
print(ans[k-1])


### FIXED CODE ###

s = input()
k = int(input())

subs_list = []
for i in range(len(s)):
    for j in range(i+1, i+k+1):
        subs_list.append(s[i:j])

ans = sorted(set(subs_list))
print(ans[k-1])