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

import heapq


n, m, s = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
change = [list(map(int, input().split())) for i in range(n)]
INF = 10 ** 18

graph = [[] for i in range(n)]
for u, v, cost, time in info:
    u -= 1
    v -= 1
    graph[u].append((v, cost, time))
    graph[v].append((u, cost, time))
    
dist = [[INF] * 3001 for i in range(n)]
dist[0][min(s, 3000)] = 0

q = [(0, min(s, 3000), 0)] # q = [(時間, 銀貨, 現在地)]
while q:
    d, gin, v = heapq.heappop(q)

    if dist[v][gin] < d:
        continue

    cc, dd = change[v]
    tmp = gin
    r = [gin]
    while True:
        if tmp + cc <= 3000:
            if dist[v][tmp + cc] > dist[v][tmp] + dd:
                dist[v][tmp + cc] = dist[v][tmp] + dd
                r.append(tmp)
            else:
                break
            tmp += cc
        else:
            break

    for nxt_v, cost, time in graph[v]:
        for g in r:
            if g - cost < 0:
                continue
            if dist[v][g] + time < dist[nxt_v][g - cost]:
                dist[nxt_v][g - cost] = dist[v][g] + time
                heapq.heappush(q, (dist[nxt_v][g - cost], g - cost, nxt_v))

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


### FIXED CODE ###

import heapq


n, m, s = map(int, input().split())
info = [list(map(int, input().split())) for i in range(m)]
change = [list(map(int, input().split())) for i in range(n)]
INF = 10 ** 18
MAX_ = 2600

graph = [[] for i in range(n)]
for u, v, cost, time in info:
    u -= 1
    v -= 1
    graph[u].append((v, cost, time))
    graph[v].append((u, cost, time))


dist = [INF] * ((MAX_ + 1) * n)
dist[min(s, MAX_)] = 0

q = [(0, min(s, MAX_), 0)] # q = [(時間, 銀貨, 現在地)]
while q:
    d, gin, v = heapq.heappop(q)

    if dist[v * (MAX_ + 1) + gin] < d:
        continue

    cc, dd = change[v]
    tmp = gin
    r = [gin]
    while True:
        if tmp + cc <= MAX_:
            if dist[v * (MAX_ + 1) + tmp + cc] > dist[v * (MAX_ + 1) + tmp] + dd:
                dist[v * (MAX_ + 1) + tmp + cc] = dist[v * (MAX_ + 1) + tmp] + dd
                r.append(tmp)
            else:
                break
            tmp += cc
        else:
            break

    for nxt_v, cost, time in graph[v]:
        for g in r:
            if g - cost < 0:
                continue
            if dist[v * (MAX_ + 1) + g] + time < dist[nxt_v * (MAX_ + 1) + g - cost]:
                dist[nxt_v * (MAX_ + 1) + g - cost] = dist[v * (MAX_ + 1) + g] + time
                heapq.heappush(q, (dist[nxt_v * (MAX_ + 1) + g - cost], g - cost, nxt_v))

for i in range(1, n):
     print(min(dist[i * (MAX_ + 1):(i + 1) * (MAX_ + 1)]))
### BUGGY CODE ###

from heapq import heappop, heappush
n = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

# B < A の要素が存在すればFalse
if any([b < a for a, b in zip(A, B)]):
  print(-1)
  exit()

# B > A の index をheapqueに入れる。
que = []
for i, (a, b) in enumerate(zip(A, B)):
  if b > a:
    heappush(que,(-b, i)) 

ans = 0
while que:
  val, idx = heappop(que)
  val *= -1
  l = idx - 1
  r = idx + 1 if idx != n - 1 else 0
  ac = B[l] + B[r]
  if val > ac:
    cnt = min((val ) // ac, (val - A[idx]) // ac)
    heappush(que, (-(val - cnt * ac), idx))
    ans += cnt
    B[idx] -= cnt * ac 

if A == B:
  print(ans)
else:
  print(-1)

  

### FIXED CODE ###

from heapq import heapify, heappop, heappush

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

q = [(-val, i) for i, val in enumerate(b) if val != a[i]]
heapify(q)

# 3print(q)

cnt = 0

while q:
  bval, i = heappop(q)
  bval = - bval - a[i]
  dv, bval = divmod(bval, b[i - 1] + b[(i + 1) % n])
#   print(dv, bval,i)
  if dv == 0:
    print(-1)
    exit()
  bval += a[i]
  b[i] = bval
  cnt += dv
  if bval != a[i]:
    heappush(q, (- bval, i))
print(cnt)
### BUGGY CODE ###

N = int(input()) # 各リストの数
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))

A.sort(reverse=False)
A.insert(0, 0)
A.append(float('inf'))
B.sort(reverse=False)

# A > B > Cである組み合わせの数を求める
count = 0
for ic in range(N):
    bottom_a = 0
    for ib in range(N):
        if B[ib] >= C[ic]:
            break
        
        top_a = N
        count_a = 0
        while top_a >= bottom_a:
            middle_a = (top_a + bottom_a) // 2

            if A[middle_a] == B[ib]:
                count_a = middle_a - 1
                break
            if A[middle_a] < B[ib] and B[ib] < A[middle_a + 1]:
                count_a = middle_a
                break
            if A[middle_a] > B[ib]:
                top_a = middle_a
            if A[middle_a] < B[ib]:
                bottom_a = middle_a + 1

        count += count_a
        bottom_a = count_a

print(count)




### FIXED CODE ###

import bisect
import itertools

N = int(input()) # それぞれのパーツの数
A = list(map(int, input().split())) # 小さい
B = list(map(int, input().split())) # 中くらい
C = list(map(int, input().split())) # 大きい

# Cは並び替え不要
A.sort()
B.sort()

# Bの各要素でAを二分探索して返ってきたindexを先に保有しておく
b_counts = [0] * N
for i in range(N):
    b_count = bisect.bisect_left(A, B[i])
    b_counts[i] = b_count

cumsum_b_counts = list(itertools.accumulate(b_counts))
cumsum_b_counts = [0] + cumsum_b_counts

# Cの各要素でBを二分探索。上記で保有しておいたb_countsを活用する
total = 0
for c in C:
    count = bisect.bisect_left(B, c)
    total += cumsum_b_counts[count]

print(total)
### BUGGY CODE ###

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

### FIXED CODE ###

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

squ = 0
num = 10 ** 9 + 7

a_sum = 0
for i_sum in range(1, n):
    a_sum += a_int[i_sum]

for i in range(0, n-1):
    squ += a_int[i] * a_sum
    a_sum -= a_int[i+1]

ans = squ % num
print(ans)
### BUGGY CODE ###

import numpy as np
from numba import jit
#@jit(cache=True)

def solve(n,k,A):
    l,r=0,0
    for ki in range(k):
        B=np.zeros(n+1,dtype=int)
        for i,j in enumerate(A):
            l=max(0,i-j)
            r=min(n,i+j+1)
            B[l]+=1
            B[r]-=1
        A=np.cumsum(B[:-1])
        np.delete(A,n-1)
    return A

n,k=map(int,input().split())
A=list(map(int,input().split()))
x=solve(n,k,A)
print(*x)

### FIXED CODE ###

import numpy as np
from numba import jit
@jit(cache = True)
def solve(n,k,A):
    l,r=0,0
    for i in range(k):
        B=np.zeros(n+1,dtype=np.int64)
        for x,y in enumerate(list(A)):
            l=max(0,x-y)
            r=min(n,x+y+1)
            B[l]+=1
            B[r]-=1
        A=np.cumsum(B[:-1])
        if A[A==n].size==n:
            break
    return A
n,k=map(int,input().split())
a=list(map(int,input().split()))
A=np.array(a)
X=solve(n,k,A)
print(*X,sep=' ')
### BUGGY CODE ###

N, K=map(int, input().split())
S=input()
A=[]
tmp=1
for i in range(1,N):
    if S[i-1]==S[i]:
        tmp+=1
    else:
        A.append(tmp)
        tmp=1
A.append(tmp)

while K>0:
    #print(A)
    K-=1
    tmpmax=0
    tmpindex=0
    if len(A)>2:
        for i in range(1,len(A)-1):
            tmp=A[i-1]+A[i]+A[i+1]
            if tmp>tmpmax:
                tmpindex=i
                tmpmax=tmp
        A[tmpindex]=tmpmax
        A.pop(tmpindex-1)
        A.pop(tmpindex)
    elif len(A)==2:
        K+=1
        break
    else: break

if len(A)>=2 and K==0:
    print(sum(A)-len(A))
else:
    print(N-1)

### FIXED CODE ###

N, K=map(int, input().split())
S=input()
A=[]
tmp=1
for i in range(1,N):
    if S[i-1]==S[i]:
        tmp+=1
    else:
        A.append(tmp)
        tmp=1
A.append(tmp)

ans=sum(A)-len(A)+(K)*2

if ans<N-1:
    print(ans)
else: print(N-1)
### BUGGY CODE ###

import bisect
x = int(input())
xx = x//2
a = []
s = 0
for i in range(x):
	s += i+1
	a.append(s)
	#print (s)

r = bisect.bisect_left(a, x)
print (r+1)


### FIXED CODE ###

import bisect
x = int(input())
xx = x//2
a = []
s = 0
for i in range(x+1):
	if (i * (i+1))/2 >= x:
		print(i)
		exit()
### BUGGY CODE ###

def main():
    import sys
    input = sys.stdin.readline
    H, W = [int(x) for x in input().strip().split()]
    Ch, Cw = [int(x)-1 for x in input().strip().split()]
    Dh, Dw = [int(x)-1 for x in input().strip().split()]
    M = [0 for _ in range(H)]
    for h in range(H):
        M[h] = list(input().strip())
        # print(M[h])
    ans = 0
    q = set([(Dh, Dw)])
    dhdw = [(1, 0), (0, 1), (-1, 0), (0, -1)]
    M[Dh][Dw] = '#'
    while True:
        newq = set()
        while q:
            q_ = set()
            for h, w in q:
                # print('({}, {}) = {}'.format(h, w, ans))
                if h == Ch and w == Cw:
                    print(ans)
                    return True
                newq.add((h, w))
                for dh, dw in dhdw:
                    if 0 <= h+dh < H and 0 <= w+dw < W:
                        if M[h+dh][w+dw] == '#':
                            continue
                        q_.add((h+dh, w+dw))
                        M[h+dh][w+dw] = '#'
            q = q_

        if newq:
            for h, w in newq:
                lh = - min(2, h)
                hh = min(3, H - h) 
                for dh in range(lh, hh):
                    lw = - min(2, w)
                    hw = min(3, W - w)
                    for dw in range(lw, hw):
                        if M[h+dh][w+dw] == '.':
                            q.add((h+dh, w+dw))
                            M[h+dh][w+dw] = '#'
        # for h in range(H):
        #     print(M[h])
        if len(q):
            ans += 1
        else:
            print(-1)
            return True

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    H, W = [int(x) for x in input().strip().split()]
    Ch, Cw = [int(x)-1 for x in input().strip().split()]
    Dh, Dw = [int(x)-1 for x in input().strip().split()]
    M = [W for _ in range(H)]
    for h in range(H):
        M[h] = list(input().strip())
        # print(M[h])
    ans = 0
    q = set([(Dh, Dw)])
    while True:
        nq = set()
        while q:
            q_ = set()
            for h, w in q:
                # print('({}, {}) = {}'.format(h, w, ans))
                if h == Ch and w == Cw:
                    print(ans)
                    return True
                M[h][w] = '#'
                nq.add((h, w))
                for dh, dw in [(1, 0), (0, 1), (-1, 0), (0, -1)]:
                    if 0 <= h+dh < H and 0 <= w+dw < W:
                        if M[h+dh][w+dw] == '.':
                            q_.add((h+dh, w+dw))
                            M[h+dh][w+dw] = '#'
            q = q_

        if nq:
            for h, w in nq:
                for dh in range(-2, 3):
                    for dw in range(-2, 3):
                        if 0 <= h+dh < H and 0 <= w+dw < W:
                            if M[h+dh][w+dw] == '.':
                                q.add((h+dh, w+dw))
        # for h in range(H):
        #     print(M[h])
        if len(q):
            ans += 1
        else:
            print(-1)
            return True

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

import itertools
H,W = map(int,input().split(' '))
bk = []
for i in range(H):
	t = input()
	bk.extend([(x,i) for x in range(W) if t[x] == '#'])

obk = set()
bk = set(bk)
cnt = 0
al = len(bk)
red = bk.copy()
while(True):
	if al == H*W:
		break
	new = set()
	for x,y in red:
		if x > 0:
			new.add((x-1,y))
		if x < W-1:
			new.add((x+1,y))
		if y > 0:
			new.add((x,y-1))
		if y < H-1:
			new.add((x,y+1))
	new -= bk
	red = new.copy()
	bk |= new
	al += len(new)
	cnt += 1
print(cnt)




### FIXED CODE ###

H,W = map(int,input().split(' '))
bk = []
for i in range(H):
	t = input()
	bk.extend([(x,i) for x in range(W) if t[x] == '#'])

mat = [[True]*H for i in [0]*W]
for x,y in bk:
	mat[x][y] = False

cnt = 0
al = len(bk)
while(True):
	if al == H*W:
		break
	new = []
	for x,y in bk:
		if x > 0 and mat[x-1][y]:
			mat[x-1][y] = False
			new.append((x-1,y))
		if x < W-1 and mat[x+1][y]:
			new.append((x+1,y))
			mat[x+1][y] = False
		if y > 0 and mat[x][y-1]:
			new.append((x,y-1))
			mat[x][y-1] = False
		if y < H-1 and mat[x][y+1]:
			new.append((x,y+1))
			mat[x][y+1] = False
	al += len(new)
	bk = new
	cnt += 1
print(cnt)
### BUGGY CODE ###

s = input()
counts = [0]*2019
counts[0] += 1
num = 0
digit = 0
for c in reversed(s):
    num += int(c) * 10**digit
    counts[num % 2019] += 1
    digit += 1
ans = 0
for count in counts:
    ans += count*(count -1) // 2
print(ans)

### FIXED CODE ###

s = input()
counts = [0]*2019
counts[0] += 1
num = 0
d = 1
for c in reversed(s):
    num += int(c) * d
    counts[num % 2019] += 1
    d *= 10
    d %= 2019
ans = 0
for count in counts:
    ans += count*(count -1) // 2
print(ans)
### BUGGY CODE ###

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

n = int(input())
a = [deque([x for x in list(map(int, input().split()))]) for _ in range(n)]

day = 1
for ii in range(3500):
  player_in_this_game = set()
  nokori_games = 0
  
  for m in range(n): #選手ごとに判定
    la = len(a[m])
    nokori_games += la #自分の残り試合予定数を足す
    if m in player_in_this_game:
      pass
    elif la: #選手に試合予定が残っている
      teki = a[m][0] #対戦相手
      jibun = m + 1 #自分
      if a[teki - 1][0] == jibun and teki - 1 not in player_in_this_game: 
      #対戦相手の予定も自分でかつ相手がこのターンで試合中ではない
        a[m].popleft() #自分の予定を消す
        a[teki - 1].popleft() #相手の予定を消す
        player_in_this_game.add(m) #自分を試合中にする
        player_in_this_game.add(teki - 1) #相手を試合中にする
        nokori_games -= 1 #残り試合予定を1つ減らす
  if nokori_games: #残り試合があるのに
    if not len(player_in_this_game): #対戦が組まれなければエラー
      print(-1)
      sys.exit()
  else: #誰も残り試合予定がなければ終了
    print(day)
    sys.exit()
  day += 1
print(-1)
sys.exit()

### FIXED CODE ###

import sys
import time
from collections import deque

start = time.time()

input = sys.stdin.readline

n = int(input())
a = [deque([x for x in list(map(int, input().split()))]) for _ in range(n)]
nokori_games = n * (n - 1) / 2 
day = 1
r5000 = range(5000)
player_in_this_game = set()
rn = range(n)
for _ in r5000:
  for m in rn: #選手ごとに判定
    #整合性のある対戦組み合わせがあれば配列から消す
    #全員の判定が終わって試合が残っていたら1日増やす
    if m in player_in_this_game:
      #自分が既に試合が組まれている
      continue

    la = len(a[m])      
    if la: #選手に試合予定が残っている
      teki = a[m][0] #対戦相手
      jibun = m + 1 #自分
      teki_idx = teki - 1
      if teki_idx in player_in_this_game:
        #相手が既に試合に組まれている
        continue

      if a[teki_idx][0] == jibun: #対戦相手の予定も自分でかつ相手がこのターンで試合中ではない
        a[m].popleft() #自分の予定を消す
        a[teki_idx].popleft() #相手の予定を消す
        player_in_this_game.add(m) #自分を試合中にする
        player_in_this_game.add(teki_idx) #相手を試合中にする
        nokori_games -= 1 #残り試合予定を1つ減らす

  if nokori_games: #残り試合があるのに
    if not len(player_in_this_game): #今回対戦が組まれなければ残りの予定が不整合なのでエラー
      print(-1)
      sys.exit()
  else: #誰も残り試合予定がなければ終了
    print(day)
    sys.exit()
  day += 1
  player_in_this_game.clear()
  elapsed_time = time.time() - start
  if elapsed_time > 1:
    print(n*(n-1)//2)
    exit()
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
import functools
INF = float("inf")


@functools.lru_cache(maxsize=None)
def power(b, p):
    if p == 0:
        return 1
    elif p == 1:
        return b

    tot = 1
    while p > 1:
        if p % 2 == 0:
            b *= b
            p //= 2
        else:
            p -= 1
            tot *= b

    return tot*b


def solve(p: int, a: "List[int]"):
    N = p
    MOD = p

    fac = [0]*N
    finv = [0]*N
    inv = [0]*N

    def cmb_init():
        fac[0] = 1
        fac[1] = 1
        finv[0] = 1
        finv[1] = 1
        inv[1] = 1
        for i in range(2, N):
            fac[i] = fac[i-1]*i % MOD
            inv[i] = -inv[MOD % i]*(MOD//i) % MOD
            finv[i] = finv[i-1]*inv[i] % MOD

    def cmb(n, k):
        if n < k:
            return 0
        if n < 0 or k < 0:
            return 0
        return fac[n] * (finv[k]*finv[n-k] % MOD) % MOD

    cmb_init()

    b = [0]*p
    for ai, av in enumerate(a):
        if av == 1:
            for i in range(p):
                b[i] += -cmb(p-1, i) * power(-ai, p-i-1)
                b[i] %= p
            b[0] += 1
            b[0] %= p
    print(*b, sep=" ")
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    p = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(p-1-0+1)]  # type: "List[int]"
    solve(p, a)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import functools
INF = float("inf")


def solve(p: int, a: "List[int]"):
    N = p+1
    MOD = p

    inv = [0]*N
    inv[1] = 1
    for i in range(2, N):
        inv[i] = -inv[MOD % i]*(MOD//i) % MOD

    b = [0]*p
    for ai, av in enumerate(a):
        if av == 0:
            continue

        c = 1
        d = 1
        for i in range(p-1, -1, -1):
            b[i] += - c * d
            b[i] %= p
            c = c * i * inv[p-i] % p
            d = -d*ai % p
        b[0] += 1
        b[0] %= p
    print(*b, sep=" ")
    return


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    p = int(next(tokens))  # type: int
    a = [int(next(tokens)) for _ in range(p-1-0+1)]  # type: "List[int]"
    solve(p, a)


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

import sys
def input():
	return sys.stdin.readline()[:-1]

n, m = map(int, input().split())
t = [list(map(int, input().split())) for _ in range(n)]
t.sort(key=lambda x:(x[1]*x[0] + x[2]*(m-x[0])), reverse=True)
full = [x[1]*x[0] + x[2]*(m-x[0]) for x in t]
cum = [0]
for i in range(n):
	cum.append(cum[-1] + full[i])
aoki = sum([p[0]*p[1] for p in t])
ans = n*m
for i in range(n):
	ok, ng = n*m, -1
	while ok-ng > 1:
		x = (ok+ng) // 2
		res = cum[x//m]
		if (x//m)-1 >= i:
			res -= full[i]
			res += full[x//m]
		res += t[i][1] * min(t[i][0], x%m) + t[i][2] * max(0, (x%m) - t[i][0])
		if res >= aoki:
			ok = x
		else:
			ng = x
	ans = min(ans, ok)
print(ans)

### FIXED CODE ###

import sys
def input():
	return sys.stdin.readline()[:-1]

n, m = map(int, input().split())
t = [list(map(int, input().split())) for _ in range(n)]
t.sort(key=lambda x:(x[1]*x[0] + x[2]*(m-x[0])), reverse=True)
full = [x[1]*x[0] + x[2]*(m-x[0]) for x in t]
cum = [0]
for i in range(n):
	cum.append(cum[-1] + full[i])
aoki = sum([p[0]*p[1] for p in t])
ans = n*m
for i in range(n):
	ok, ng = n*m, -1
	while ok-ng > 1:
		x = (ok+ng) // 2
		res = cum[x//m]
		if (x//m)-1 >= i:
			res -= full[i]
			res += full[x//m]
		res += t[i][1] * min(t[i][0], x%m) + t[i][2] * max(0, (x%m) - t[i][0])
		if res >= aoki:
			ok = x
		else:
			ng = x
	ans = min(ans, ok)
print(ans)
### BUGGY CODE ###

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

### FIXED CODE ###

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

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

paper = []

for a in A:
  if a in paper:
    paper.remove(a)
  else:
    paper.append(a)

print(len(paper))

### FIXED CODE ###

from collections import Counter

n = int(input())
inputs = [int(input()) for _ in range(n)]
counter = Counter(inputs)

answer = 0
for number, count in counter.items():
    if count % 2 != 0:
        answer += 1

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

import sys

sys.setrecursionlimit(10 ** 9)
def solve(pick, idx):

    if pick == 0: return 0
    if idx >= n: return -float('inf')
    if (pick, idx) in dp: return dp[pick, idx]
    # if n-idx+2 < pick*2: return -float('inf')
    total = max(A[idx] + solve(pick-1, idx+2), solve(pick, idx+1))

    dp[(pick, idx)] = total
    return total

n = int(input())
A = list(map(int, input().split()))
dp = {}
pick = n//2

print(solve(pick, 0))

### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 9)
def solve(pick, idx):

    if pick == 0: return 0
    if idx >= n: return -float('inf')
    if (pick, idx) in dp: return dp[pick, idx]
    if n-idx+2 < pick*2: return -float('inf')
    total = max(A[idx] + solve(pick-1, idx+2), solve(pick, idx+1))

    dp[(pick, idx)] = total
    return total

n = int(input())
A = list(map(int, input().split()))
dp = {}
pick = n//2

print(solve(pick, 0))
### BUGGY CODE ###

#!python3

iim = lambda: map(int, input().rstrip().split())

from collections import deque

def resolve():
    H, W = iim()

    M = [input() for i in range(H)]

    def search(y, x):
        q = []
        m = [[0]*W for i in range(H)]

        q = deque([(y,x, 0)])
        ans = 0
        while q:
            y, x, k = q.popleft()
            m[y][x] = 1
            ans = max(ans, k)
            for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                yy = y + i
                xx = x + j

                if 0 <= xx < W and 0 <= yy < H:
                    if M[yy][xx] == "." and m[yy][xx] == 0:
                        q.append((yy, xx, k+1))

        return ans

    ans = 0
    for y in range(H):
        for x in range(W):
            if M[y][x] == ".":
                ans = max(ans, search(y, x))
    print(ans)
if __name__ == "__main__":
    resolve()


### FIXED CODE ###

#!python3

iim = lambda: map(int, input().rstrip().split())

from collections import deque

def resolve():
    H, W = iim()

    M = [input() for i in range(H)]

    def search(y, x):
        q = []
        m = [[0]*W for i in range(H)]

        m[y][x] = 1
        q = deque([(y,x, 0)])
        ans = 0
        while q:
            y, x, k = q.popleft()
            ans = max(ans, k)
            for i, j in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                yy = y + i
                xx = x + j

                if 0 <= xx < W and 0 <= yy < H:
                    if M[yy][xx] == "." and m[yy][xx] == 0:
                        m[yy][xx] = 1
                        q.append((yy, xx, k+1))

        return ans

    ans = 0
    for y in range(H):
        for x in range(W):
            if M[y][x] == ".":
                ans = max(ans, search(y, x))
    print(ans)
if __name__ == "__main__":
    resolve()
### BUGGY CODE ###

s = input()
K = int(input())

sub = set()
for i in range(1, len(s) + 1):
    for k in range(len(s) - i + 1):
        sub.add(s[k:i + k])

print(sorted([i for i in sub])[K - 1])


### FIXED CODE ###

s = input()
K = int(input())

sub = set()
for i in range(1, K + 1):
    for k in range(len(s) - i + 1):
        sub.add(s[k:i + k])

print(sorted([i for i in sub])[K - 1])
### BUGGY CODE ###

import itertools
import sys
input = sys.stdin.readline

S = list(map(int, list(input().rstrip('\n'))))
temp = S.copy()

for k in itertools.count():
    for i in range(len(temp) - 1):
        if temp[i] != temp[i + 1]:
            temp.pop(i)
            temp.pop(i)
            break
    if temp.count(0) == len(temp) or temp.count(1) == len(temp):
        break

print(len(S)-len(temp))


### FIXED CODE ###

import itertools
import sys
input = sys.stdin.readline

S = input().rstrip('\n')
N = len(S)

print(2*min(S.count('0'), S.count('1')))

# for i in itertools.count():
#     # print(S)
#     S = S.replace('01', '').replace('10', '')
#     if not S:
#         break
#     if S.count('0') == 0 or S.count('1') == 0:
#         break

# print(N-len(S))