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

from collections import deque
a,b=map(int,input().split())
c=[list(map(int,input().split())) for i in range(a-1)]

e=[[]for i in range(a)]

for i in c:
  e[i[0]-1].append(i[1]-1)
  e[i[1]-1].append(i[0]-1)


g=[[]for i in range(a)]
f=deque()
f.append((0,-1))
ans=[0 for _ in range(a)]
for i in range(b):
  ten,p=map(int,input().split())
  ans[ten-1]+=p
i=0
while len(f)!=0:
  i,fr=f.popleft()
  for j in e[i]:
    if j==fr:
      continue
    else:
      ans[j]+=ans[i]
      f.append([j,i]) 
print(*ans)
    
  

  
  


### FIXED CODE ###

from collections import deque
a,b=map(int,input().split())
e=[[]for i in range(a)]

for i in range(a-1):
  c1,c2=map(int,input().split())
  e[c1-1].append(c2-1)
  e[c2-1].append(c1-1)

g=[[]for i in range(a)]
f=deque()
f.append((0,-1))
ans=[0 for _ in range(a)]
for i in range(b):
  ten,p=map(int,input().split())
  ans[ten-1]+=p
i=0
while len(f)!=0:
  i,fr=f.popleft()
  for j in e[i]:
    if j==fr:
      continue
    else:
      ans[j]+=ans[i]
      f.append([j,i]) 
print(*ans)
### BUGGY CODE ###

S = input()
n = len(S)
count = 0
T = [0] * (n + 1)
mods = [0] * (n + 1)
mod_dict = {i:0 for i in range(2019)}
mod_dict[0] = 1
for i in reversed(range(n)):
    mods[i] = (mods[i+1] + (int(S[i]) * (10 ** (n - i -1)))) % 2019
    mod_dict[mods[i]] = mod_dict[mods[i]] + 1

count = 0
for k, v in mod_dict.items():
    count = count + int(v*(v-1)/2)

print(count)


### FIXED CODE ###

reverse_S = input()[::-1]
n = len(reverse_S)
count = 0
mod = 0
mods = [0] * 2019
mods[0] = 1
x = 1
for s in reverse_S:
    mod = (mod + (int(s) * x)) % 2019
    mods[mod] = mods[mod] + 1
    x = x * 10
    x = x % 2019

for v in mods:
    count = count + v*(v-1)//2

print(count)
### BUGGY CODE ###

R, G, B, N = map(int, input().split())
cnt = 0
for i in range(N // R + 1):
    for j in range(N // G + 1):
        q, mod = divmod((N - R * i - G * j), B)
        if q >= 0 and mod == 0:
            cnt += 1
print(cnt)


### FIXED CODE ###

R, G, B, N = map(int, input().split())
cnt = 0

for i in range(N // R + 1):
    for j in range(N // G + 1):
        if (N - R * i - G * j) / B >= 0 and ((N - R * i - G * j) / B) % 1 == 0:
            cnt += 1
print(cnt)
### BUGGY CODE ###

import heapq

from operator import itemgetter

n,m = map(int,input().split())

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

info = [0] * m
for i in range(m):
    info[i] = list(map(int,input().split()))

info = sorted(info,key = itemgetter(1),reverse = True)
reinfo = info[0:n]
#print(a)

heapq.heapify(a)
#print(a)

d = 0

for j in range(len(reinfo)):
    for k in range(reinfo[j][0]):
        if a[0] > reinfo[j][1]:
            d = 1
            break
        else:
            heapq.heappushpop(a,reinfo[j][1])
    if d == 1:
        break

print(sum(a))

### FIXED CODE ###

import heapq

from operator import itemgetter

n,m = map(int,input().split())

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

info = [0] * m
for i in range(m):
    info[i] = list(map(int,input().split()))

info = sorted(info,key = itemgetter(1),reverse = True)
#print(a)

heapq.heapify(a)
#print(a)

d = 0
count = 0

for j in range(len(info)):
    for k in range(info[j][0]):
        if a[0] > info[j][1]:
            d = 1
            break
        else:
            heapq.heappushpop(a,info[j][1])
            count += 1
        if count >= n:
            d = 1
            break
    if d == 1:
        break

print(sum(a))
### BUGGY CODE ###

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

c = 0
for i in range(N):
    flag = 1
    for j in range(i):
        if P[j] < P[i]: 
            flag = 0 
            break
    if flag > 0:
        c += 1

print(c)

### FIXED CODE ###

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

c = 0
for i in range(N - 1):
    f = P[i]
    l = P[i + 1]
    if f < l:
        P[i] = l
        P[i+1] = f
        c += 1

print(N - c)
### BUGGY CODE ###

a,b,x = map(int,input().split())
cnt = 0
for i in range(a,b+1):
    if i%x==0:
        cnt += 1
print(cnt)

### FIXED CODE ###

a,b,x = map(int,input().split())
cnt = b//x
cnt1 = (a-1)//x
print(cnt-cnt1)
### BUGGY CODE ###

n = int(input())
ga, sa, ba = map(int, input().split())
gb, sb, bb = map(int, input().split())

dp1 = [0] * (n + 1)
if n > 5001:
    for i in range(1, 5001):
        feat = [i]
        if i - ga >= 0:
            feat.append(dp1[i-ga]+gb)
        if i - sa >= 0:
            feat.append(dp1[i-sa]+sb)
        if i - ba >= 0:
            feat.append(dp1[i-ba]+bb)
        dp[i] = max(feat)
    for i in range(5001, n+1):
        dp1[i] = max(i, dp1[i-ga]+gb, dp1[i-sa]+sb, dp1[i-ba]+bb)
else:
    for i in range(1, n+1):
        feat = [i]
        if i - ga >= 0:
            feat.append(dp1[i-ga]+gb)
        if i - sa >= 0:
            feat.append(dp1[i-sa]+sb)
        if i - ba >= 0:
            feat.append(dp1[i-ba]+bb)
        dp1[i] = max(feat)

B = dp1[-1]
dp2 = [0] * (B + 1)
if n > 5001:
    for i in range(1, 5001):
        feat = [i]
        if i - gb >= 0:
            feat.append(dp2[i-gb]+ga)
        if i - sb >= 0:
            feat.append(dp2[i-sb]+sa)
        if i - bb >= 0:
            feat.append(dp2[i-bb]+ba)
        dp2[i] = max(feat)

    for i in range(5001, B+5001):
        dp2[i] = max(i-5000, dp2[i-gb]+ga, dp2[i-sb]+sa, dp2[i-bb]+ba)
else:
    for i in range(1, B+1):
        feat = [i]
        if i - gb >= 0:
            feat.append(dp2[i-gb]+ga)
        if i - sb >= 0:
            feat.append(dp2[i-sb]+sa)
        if i - bb >= 0:
            feat.append(dp2[i-bb]+ba)
        dp2[i] = max(feat)

print(dp2[-1])


### FIXED CODE ###

n = int(input())
ga, sa, ba = map(int, input().split())
gb, sb, bb = map(int, input().split())

dp1 = [0] * (n + 1)
if n > 5001:
    for i in range(1, 5001):
        feat = [i]
        if i - ga >= 0:
            feat.append(dp1[i-ga]+gb)
        if i - sa >= 0:
            feat.append(dp1[i-sa]+sb)
        if i - ba >= 0:
            feat.append(dp1[i-ba]+bb)
        dp[i] = max(feat)
    for i in range(5001, n+1):
        dp1[i] = max(i, dp1[i-ga]+gb, dp1[i-sa]+sb, dp1[i-ba]+bb)
else:
    for i in range(1, n+1):
        feat = [i]
        if i - ga >= 0:
            feat.append(dp1[i-ga]+gb)
        if i - sa >= 0:
            feat.append(dp1[i-sa]+sb)
        if i - ba >= 0:
            feat.append(dp1[i-ba]+bb)
        dp1[i] = max(feat)

B = dp1[-1]
dp2 = [0] * (B + 1)
if B > 5001:
    for i in range(1, 5001):
        feat = [i]
        if i - gb >= 0:
            feat.append(dp2[i-gb]+ga)
        if i - sb >= 0:
            feat.append(dp2[i-sb]+sa)
        if i - bb >= 0:
            feat.append(dp2[i-bb]+ba)
        dp2[i] = max(feat)

    for i in range(5001, B+1):
        dp2[i] = max(i, dp2[i-gb]+ga, dp2[i-sb]+sa, dp2[i-bb]+ba)
else:
    for i in range(1, B+1):
        feat = [i]
        if i - gb >= 0:
            feat.append(dp2[i-gb]+ga)
        if i - sb >= 0:
            feat.append(dp2[i-sb]+sa)
        if i - bb >= 0:
            feat.append(dp2[i-bb]+ba)
        dp2[i] = max(feat)

print(dp2[-1])
### BUGGY CODE ###

def main():
    N = int(input())
    P = tuple(map(int,input().split()))
    a = 0
    for i in range(N):
        hantei = 0
        if i == 0:
            pass
        else:
            if min(P[:i]) < P[i]:
                hantei = 1
        if hantei == 0:
            a += 1
    print(a)
if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    N = int(input())
    P = tuple(map(int,input().split()))
    a = 1
    minP = P[0]
    for i in range(1, N):
        if minP < P[i]:
            pass
        else:
            minP = P[i]
            a += 1
    print(a)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

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

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a
if N<=2:
    print(max(A))
else:
    gcds = []
    for n in range(N):
        if n == 0:
            lgcd = None
        else:
            lgcd = A[0]
            for i in range(n):
                lgcd = gcd(lgcd,A[i])
        if n == N-1:
            rgcd = None
        else:
            rgcd = A[n+1]
            for i in range(n+1,N):
                rgcd = gcd(rgcd,A[i])
        if lgcd == None:
            gcds.append(rgcd)
        elif rgcd == None:
            gcds.append(lgcd)
        else:
            gcds.append(gcd(lgcd,rgcd))
    print(max(gcds))

### FIXED CODE ###

N = int(input())
A = [int(i) for i in input().split()]
def gcd(a, b):
    while b:
        a, b = b, a % b
    return a  
lgcds = [A[0]]
rgcds = [A[N-1]]
for n in range(N-2):
    lgcds.append(gcd(lgcds[-1],A[n+1]))
    rgcds.append(gcd(rgcds[-1],A[-2-n]))
gcds = [lgcds[-1],rgcds[-1]]
for i in range(N-2):
    gcds.append(gcd(lgcds[i],rgcds[-2-i]))
print(max(gcds))
### BUGGY CODE ###

L,R = list(map(int,input().split()))
lt = []
for k in range(L,R+1):
    if k % 2019 == 0:
        print(0)
else:
    for i in range(L,R+1):
        for j in range(i+1,R+1):
            s = 0
            t = 0
            s = i % 2019 
            t = j % 2019
            ans = (s*t) % 2019
            lt.append(ans)
    print(min(lt))

### FIXED CODE ###

L,R = list(map(int,input().split()))
lt = []
if R-L == 1:
    print((L*R) % 2019)
elif R-L >= 2:
    for k in range(L,R+1):
        if k % 673 == 0:
            lt.append(0)
            break
    l = L % 673
    r = R % 673
    for i in range(l,r+1):
        for j in range(i+1,r+1):
            ans = (i*j) % 2019
            lt.append(ans)
    print(min(lt))
### BUGGY CODE ###


import sys 
input = sys.stdin.readline
def dijkstra(s,n,w,cost):
    #始点sから各頂点への最短距離
    #n:頂点数,　w:辺の数, cost[u][v] : 辺uvのコスト(存在しないときはinf)
    d = [float("inf")] * n
    used = [False] * n
    d[s] = 0
    
    while True:
        v = -1
        #まだ使われてない頂点の中から最小の距離のものを探す
        for i in range(n):
            if (not used[i]) and (v == -1):
               v = i
            elif (not used[i]) and d[i] < d[v]:
                v = i
        if v == -1:
               break
        used[v] = True
               
        for j in range(n):
               d[j] = min(d[j],d[v]+cost[v][j])
    return d
def solve():
  n = int(input())
  d = [[float("inf")]*n for _ in range(n)]
  for i in range(n-1):
    a,b,c = (int(i) for i in input().split())
    d[a-1][b-1] = c
    d[b-1][a-1] = c

  q,k = (int(i) for i in input().split())
  
  d = dijkstra(k-1,n,n-1,d)

  for i in range(q):
    x,y = (int(i) for i in input().split())
    print(int(d[x-1] + d[y-1]))

solve()

### FIXED CODE ###


import sys 
input = sys.stdin.readline
from collections import deque
def solve():
  n = int(input())
  d = [[]*n for _ in range(n)]
  for i in range(n-1):
    a,b,c = (int(i) for i in input().split())
    d[a-1].append((b-1,c))
    d[b-1].append((a-1,c))
  q,k = (int(i) for i in input().split())
  #kからの距離を計算する
  d2 = [10**10]*n
  visit = [False]*n
  query = deque([(k-1,0)]) #始点、距離
  while query:
    place,dist = query.pop()
    if visit[place]:
      continue
    else:
      visit[place] = visit
      d2[place] = dist
      for i in range(len(d[place])):
        np,nc = d[place][i]
        if not visit[np]:
          query.append((np,nc+dist))
  for i in range(q):
    x,y = (int(i) for i in input().split())
    print(int(d2[x-1] + d2[y-1]))

solve()
### BUGGY CODE ###

def f(index, num):
  for k in range(13):
    a[index][(k*10+num)%13]+=a[index-1][k]
    a[index][(k*10+num)%13]%=MOD

S=input()
N=len(S)
if N==1:
  if S=='?' or int(S)==5:
    print(1)
  else:
    print(0)
  exit()
  
MOD=10**9+7

a=[[0]*13 for i in range(N)]
if S[0]=='?':
  a[0]=[1]*10+[0]*3
else:
  a[0][int(S[0])]=1

for i in range(1, N):
  if S[i]=='?':
      f(i, 0)
      f(i, 1)
      f(i, 2)
      f(i, 3)
      f(i, 4)
      f(i, 5)
      f(i, 6)
      f(i, 7)
      f(i, 8)
      f(i, 9)
  else:
    f(i, int(S[i]))
    
print(a[-1][5])

### FIXED CODE ###

def f(index, num):
  for k in range(13):
    a[index][(k*10+num)%13]+=a[index-1][k]

S=input()
N=len(S)
if N==1:
  if S=='?' or int(S)==5:
    print(1)
  else:
    print(0)
  exit()
  
MOD=10**9+7

a=[[0]*13 for i in range(N)]
if S[0]=='?':
  a[0]=[1]*10+[0]*3
else:
  a[0][int(S[0])]=1

for i in range(1, N):
  if S[i]=='?':
    for j in range(10):
      f(i, j)
    for j in range(13):
      a[i][j]%=MOD
  else:
    f(i, int(S[i]))
    
print(a[-1][5])
### BUGGY CODE ###

n = int(input())
cnt = 0
A = []
for _ in range(n):
    A.append([sorted(input())]) 
for i in range(n-1):
    s = sorted(A[i])
    for j in range(i+1, n):
        t = sorted(A[j])
        if s == t:
            cnt += 1
print(cnt)
         

### FIXED CODE ###

n = int(input())
cnt = 0
A = []
for _ in range(n):
    t = sorted(input())
    t = "".join(t)
    A.append(t)

import collections
C = collections.Counter(A)
lC = list(C.values())
for i in lC:
    cnt += i * (i-1) // 2
print(cnt)
### BUGGY CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

k = int(input())
ans = 0
for a in range(1,k+1):
    for b in range(1, k+1):
        for c in range(1, k+1):
            ans += gcd(a,b,c)
print(ans)

### FIXED CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

k = int(input())
ans = 0
for a in range(1,k+1):
    for b in range(a, k+1):
        for c in range(b, k+1):
            if a == b and b == c:
                ans += gcd(a,b,c)
            elif (a == b and b != c) or (a != b and b == c):
                ans += gcd(a,b,c) * 3
            elif a != b and b != c:
                ans += gcd(a,b,c) * 6
            else:
                print('error')
print(ans)
### BUGGY CODE ###

from collections import defaultdict

N, M = map(int, input().split())
A = list(map(int, input().split()))
A = [a % M for a in A]

dp = [defaultdict(int) for _ in range(N + 1)]

for i, a in enumerate(A, start=1):
    dp[i][a] += 1
    for s, cnt in dp[i - 1].items():
        dp[i][(s + a) % M] += cnt

ans = 0
for cnt in dp[1:]:
    ans += cnt[0]

print(ans)

### FIXED CODE ###

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

S = [0] * (N+1)
for i in range(N) :
    S[i+1] = S[i] + A[i]

cat = {}
for s in S :
    mod = s % M
    if mod in cat :
        cat[mod] += 1
    else :
        cat[mod] = 1

def comb(n, k) :
    p = 1
    d = 1
    for i in range(k) :
        p *= (n - i)
        d *=(i + 1)
    return p // d

ans = 0
for key, val in cat.items() :
    if val < 2 :
        continue
    ans += comb(val, 2)

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

n = int(input())
A = list(map(int,input().split()))
S = 1
for i in range(n):
    S = S * A[i]
if S > 10**18:
    print(-1)
else:
    print(S)

### FIXED CODE ###

import sys
l = 10**18
n = int(input())
A = list(map(int,input().split()))
S = 1
if 0 in A:
    print(0)
    sys.exit()
for i in range(n):
    S = S * A[i]
    if S > l:
        print(-1)
        break
if S <= l:
    print(S)
### BUGGY CODE ###

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

### FIXED CODE ###

mod = 10**9+7
n = int(input())
input_list = list(map(int,input().split()))
input_len = len(input_list)
remain_num = sum(input_list[1:])
remain_list = [remain_num]
for i in range(1,input_len):
    remain_list.append(remain_list[i-1]-input_list[i])

temp = 0
for i in range(input_len):
    temp = (temp+input_list[i]*remain_list[i])%mod
print(temp)
### BUGGY CODE ###

n = int(input())
a = list(int(input()) for _ in range(n))
for i in range(n):
    aa = a.copy()
    del aa[i]
    print(max(aa))

### FIXED CODE ###

n = int(input())
a = list(int(input()) for _ in range(n))
aa = sorted(a.copy())
mx, sd = aa[n - 1], aa[n - 2]
for i in a:
    print(mx if i < mx else sd)
### BUGGY CODE ###

K,S = map(int,input().split())
count1 = 0
count2 = 0
count3 = 0
for x in range(0,K+1):
    for y in range(x,K+1):
        for z in range(y,K+1):
            if x+y+z==S:
                if x==y and y==z and z==x:
                    count1+=1
                elif x!=y and y!=z and z!=x:
                    count2+=1
                else:
                    count3+=1
sum = count1+count2*6+count3*3
print(sum)

### FIXED CODE ###

K,S = map(int,input().split())
sum=0
for x in range(0,K+1):
    for y in range(0,K+1):
        z = S-x-y

        if z>=0 and z<=K:
            sum+=1


print(sum)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *


def solve(H: int, W: int, A: "List[str]"):
    queue = deque()

    rem = H * W
    for i in range(H):
        for j in range(W):
            if A[i][j] == '#':
                queue.append((i, j, 0))

    ret = 0
    visited = [[False] * W for _ in range(H)]
    while 0 < len(queue):
        i, j, n = queue.popleft()
        if visited[i][j]:
            continue
        visited[i][j] = True
        ret = max(ret, n)
        rem -= 1
        if rem == 0:
            break

        if 0 < j:
            queue.append((i, j - 1, n + 1))
        if j < W - 1:
            queue.append((i, j + 1, n + 1))
        if 0 < i:
            queue.append((i - 1, j, n + 1))
        if i < H - 1:
            queue.append((i + 1, j, n + 1))
    return ret


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    A = [ next(tokens) for _ in range(H) ]  # type: "List[str]"
    result = solve(H, W, A)
    print(result)

if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env python3
import sys
from math import *
from itertools import *
from collections import *
from functools import *
from operator import *


def solve(H: int, W: int, A: "List[str]"):
    queue = deque()

    rem = H * W
    visited = [True] * ((W+2) * (H+2))
    for i in range(W+2):
        visited[i] = False
        visited[(W + 2) * (H + 1) + i] = False
    for i in range(H+2):
        visited[(W + 2) * i] = False
        visited[(W + 2) * i + (W + 1)] = False

    for i in range(H):
        l = A[i]
        for j in range(W):
            if l[j] == '#':
                queue.append((i+1, j+1, 0))
                k = i * (W + 2) + j
                visited[k] = False

    ret = 0
    while queue:
        i, j, n = queue.popleft()
        k = i * (W + 2) + j
        if not visited[k] and 0 < n:
            continue
        visited[k] = False
        ret = n
        rem -= 1

        if rem == 0:
            break

        if visited[k - 1]:
            queue.append((i, j - 1, n + 1))
        if visited[k + 1]:
            queue.append((i, j + 1, n + 1))

        if visited[k - (W + 2)]:
            queue.append((i - 1, j, n + 1))
        if visited[k + (W + 2)]:
            queue.append((i + 1, j, n + 1))
    return ret


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    H = int(next(tokens))  # type: int
    W = int(next(tokens))  # type: int
    A = [ next(tokens) for _ in range(H) ]  # type: "List[str]"
    result = solve(H, W, A)
    print(result)

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

import sys
import math
sys.setrecursionlimit(20000000)
input = sys.stdin.readline
x,y,z,p = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))
a.sort()
b.sort()
c.sort()
"""
if x*y*z <= 3*10**6:
    abc = []
    for i in range(x):
        for j in range(y):
            for k in range(z):
                abc.append(a[i]+b[j]+c[k])
    abc.sort()
    abc = abc[::-1]
    for i in range(p):
        print(abc[i])  
    exit()
"""
ab = []
for i in range(x):
    for j in range(y):
        ab.append(a[i]+b[j])
ab.sort()
c = c[::-1]
ab = ab[::-1]
ab.append(-2**62)
ans = []
miru = [0]*z
for i in range(z):
    if i + 1 == z:
        d = -2**60
    else:
        d = c[i+1]+ab[0]
    for j in range(i+1):
        flag = 0
        while ab[miru[j]] + c[j] >= d and (len(ans)<= p or ab[miru[j]] + c[j] >= ans[0]):
             ans.append(ab[miru[j]] + c[j])
             miru[j]+=1
             flag = 1
        if flag and len(ans) >p:
            ans.sort()
ans.sort()
ans = ans[::-1]
for i in range(p):
    print(ans[i])

### FIXED CODE ###

import sys
import math
sys.setrecursionlimit(20000000)
input = sys.stdin.readline
x,y,z,p = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))
a.sort()
b.sort()
c.sort()
"""
if x*y*z <= 3*10**6:
    abc = []
    for i in range(x):
        for j in range(y):
            for k in range(z):
                abc.append(a[i]+b[j]+c[k])
    abc.sort()
    abc = abc[::-1]
    for i in range(p):
        print(abc[i])  
    exit()
"""
ab = []
for i in range(x):
    for j in range(y):
        ab.append(a[i]+b[j])
ab.sort()
c = c[::-1]
ab = ab[::-1]
ab.append(-2**62)
ans = []
miru = [0]*z
for i in range(z):
    if i + 1 == z:
        d = -2**60
    else:
        d = c[i+1]+ab[0]
    for j in range(i+1):
        flag = 0
        while ab[miru[j]] + c[j] >= d and (len(ans)<= p or ab[miru[j]] + c[j] >= ans[0]):
             ans.append(ab[miru[j]] + c[j])
             miru[j]+=1
             flag = 1
        if flag and len(ans) <=p+1:
            ans.sort()
ans.sort()
ans = ans[::-1]
for i in range(p):
    print(ans[i])
### BUGGY CODE ###

from collections import deque
import math
import copy
H,W = map(int,input().split())
maze = [list(input()) for _ in range(H)]

def bfs(maze,h,w,sx,sy,gx,gy):
    for y in range(h):
        for x in range(w):
            if maze[y][x]=='.':
                maze[y][x]=float('inf')

    maze[sy][sx]=0
    que=deque([[sy,sx]])
    while que:
        y,x=que.popleft()
        for i,j in [(1,0),(0,1),(-1,0),(0,-1)]:
            if 0 <= y+i < H and 0<=x+j<W:
                nexty,nextx=y+i,x+j
                dist=maze[nexty][nextx]
                if dist!='#':
                    if dist>maze[y][x]+1:
                        maze[nexty][nextx]=maze[y][x]+1
                        que.append([nexty,nextx])
    return maze[gy][gx]
max_dist = -1  
for si in range(H):
  for sj in range(W):
    if maze[si][sj] == '#':
      continue
    for gi in range(H):
      for gj in range(W):
        if maze[gi][gj] == '#' or (si == gi and sj == gj):
          continue
        copymaze = copy.deepcopy(maze)
        res =  int(bfs(copymaze,H,W,sj,si,gj,gi))
        max_dist = max(max_dist,res)

print(max_dist)

### FIXED CODE ###

from collections import deque
import math
import copy
H,W = map(int,input().split())
maze = [list(input()) for _ in range(H)]
def bfs(maze,h,w,sx,sy):
    for y in range(h):
        for x in range(w):
            if maze[y][x]=='.':
                maze[y][x]=float('inf')

    maze[sy][sx]=0
    que=deque([[sy,sx]])
    while que:
        y,x=que.popleft()
        for i,j in [(1,0),(0,1),(-1,0),(0,-1)]:
            if 0 <= y+i < H and 0<=x+j<W:
                nexty,nextx=y+i,x+j
                dist=maze[nexty][nextx]
                if dist!='#':
                    if dist>maze[y][x]+1:
                        maze[nexty][nextx]=maze[y][x]+1
                        que.append([nexty,nextx])
    m = 0                   
    for l in maze:
      li = [i for i in l if i != '#' and i < 1000000]
      if len(li) > 0:
        m = max(m,max(li))
    return m
max_dist = -1  
for si in range(H):
  for sj in range(W):
    if maze[si][sj] == '#':
      continue
    copymaze = copy.deepcopy(maze)
    res = bfs(copymaze,H,W,sj,si)
    max_dist = max(max_dist,res)
print(max_dist)