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

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


N = int(input())

cost = [[float("inf") for i in range(N)] for j in range(N)]
for i in range(N-1):
    a, b, c = map(int, input().split())
    cost[a-1][b-1] = c
    cost[b-1][a-1] = c

Q, K = map(int, input().split())
    
ans = dijkstra(K-1, N, N-1, cost)
for i in range(Q):
    x, y = map(int, input().split())
    print(ans[x-1] + ans[y-1])


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)

N = int(input())
tree = [[] for _ in range(N)]
for i in range(N-1):
    a, b, c = map(int, input().split())
    tree[a-1].append([b-1, c])
    tree[b-1].append([a-1, c])
Q, K = map(int, input().split())

dist = [-1] * N
def dfs(v, total_cost):
    # v：頂点, total_cost：今までかかったコストの合計
    dist[v] = total_cost
    for v_next, cost in tree[v]:
        if dist[v_next] >= 0:
            continue
            # v_nextが訪問済みならスキップ
        dfs(v_next, total_cost+cost)

dfs(K-1, 0)

for i in range(Q):
    x, y = map(int, input().split())
    print(dist[x-1] + dist[y-1])
### BUGGY CODE ###

n=int(input())
A=list(input().split())
B=[]
import queue
q=queue.Queue()
for a in A:q.put(a)
while not q.empty():
    B.append(q.get())
    B=B[::-1]
print(*B)
    

### FIXED CODE ###

n = int(input())
a = list(input().split())
a1 = ['']*(n//2 + n%2)
a2 = ['']*(n//2)

for i in range(n):
	if i%2 == 0:
		a1[i//2] = a[i]
	else:
		a2[-i//2] = a[i]

if n%2 != 0 and n != 1:
	ans = ' '.join(a1[::-1]) + ' ' + ' '.join(a2[::-1])
elif n%2 == 0:
	ans = ' '.join(a2) + ' ' + ' '.join(a1)
else:
	ans = a[0]
print(ans)
### BUGGY CODE ###

import heapq
N = int(input())
A = []
for _ in range(N):
    A.append((-1) * int(input()))

for i in range(N):
    list = A[:i] + A[i + 1:]
    heapq.heapify(list)
    print((-1) * heapq.heappop(list))

### FIXED CODE ###

N = int(input())
A = []
for _ in range(N):
    A.append(int(input()))
list = A
list = sorted(list)
max = list[-1]
second_max = list[-2]
cnt = A.count(max)
for i in range(N):
    if A[i] == max and  cnt == 1:
        print(second_max)
    else:
        print(max)
### BUGGY CODE ###

from math import sqrt
a,b=map(int,input().split())
c=a*b
for i in range(1,int(sqrt(max(a,b)))):
  while a%i==0 and b%i == 0:
    c=c/i
    
print(c)

### FIXED CODE ###

import fractions
a,b=map(int,input().split())
c=fractions.gcd(a,b)
print(int(a*b/c))
### BUGGY CODE ###

n,W = map(int, input().split())
l = [dict() for i in range(n+1)]
l[0][0] = 0
for i in range(1,n+1):
  w,v = map(int, input().split())
  l[i] = l[i-1].copy()
  l[i][w] = max(l[i].get(w,0),v)
  for x in l[i-1]:
    if x+w <= W:
      l[i][x+w] = max(l[i].get(x+w,0),l[i-1][x] + v)
print(max(l[n].values()))

### FIXED CODE ###

n,W = map(int, input().split())
l = [dict() for i in range(n+1)]
l[0][0] = 0
for i in range(1,n+1):
  w,v = map(int, input().split())
  l[i] = l[i-1].copy()
  l[i][w] = max(l[i].get(w,0),v)
  for x in l[i-1]:
    if x+w <= W:
      l[i][x+w] = max(l[i].get(x+w,0),l[i-1][x] + v)
print(max(l[n].values()))
### BUGGY CODE ###

import queue

def bfs(s1,s2):
    queueX = queue.Queue()
    queueY = queue.Queue()
    queueX.put(s1)
    queueY.put(s2)
    #s[s1][s2] = 0
    #while queueX.empty() == False:
    x = queueX.get()
    y = queueY.get()

    for i in range(4):
        nextX = x + moveR[i]
        nextY = y + moveC[i]
        if 0 <= nextX and nextX < H\
            and 0 <= nextY and nextY < W\
            and s[nextX][nextY] != '#'\
            and s[nextX][nextY] == '.':
            s[nextX][nextY] = '#'
            queueX.put(nextX)
            queueY.put(nextY)

H, W = map(int, input().split())
s = [list(input()) for _ in range(H)]
moveR = [0, 1, -1, 0]
moveC = [1, 0, 0, -1]

ans = 0
while True:
    cnt = 0
    cntlst = []
    for i in range(H):
        for j in range(W):
            if s[i][j] == '#':
                cntlst.append([i, j])
                cnt += 1
    if cnt == (H * W):
        break
    for i in cntlst:
        bfs(i[0], i[1])
    ans += 1

print(ans)


### FIXED CODE ###

from collections import deque

def bfs():
    while len(que) != 0:
        p = que.popleft()
        for i in range(4):
            nextX = p[0] + moveR[i]
            nextY = p[1] + moveC[i]
            if 0 <= nextX and nextX < H\
                and 0 <= nextY and nextY < W\
                and s[nextX][nextY] != '#'\
                and s[nextX][nextY] == '.':
                s[nextX][nextY] = s[p[0]][p[1]] + 1
                que.append([nextX, nextY])

H, W = map(int, input().split())
s = [list(input()) for _ in range(H)]
moveR = [0, 1, -1, 0]
moveC = [1, 0, 0, -1]

que = deque()
for i in range(H):
    for j in range(W):
        if s[i][j] == '#':
            que.append([i, j])
            s[i][j] = 0
bfs()
ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, s[i][j])
print(ans)
### BUGGY CODE ###

N, K = [int(_) for _ in input().split()]
H = [int(_) for _ in input().split()]
list_H = sorted(H, reverse=True)
if len(H) < K:
    print(0)
else:
    for k in range(K):
        if len(list_H) > 0:
            list_H.pop(0)
    print(sum(list_H))


### FIXED CODE ###

N, K = [int(_) for _ in input().split()]
H = [int(_) for _ in input().split()]
H.sort(reverse=True)
print(sum(H[K:]))
### BUGGY CODE ###

tmp=input()
l=[int(tmp[i:]) for i in reversed(range(len(tmp)))]
cnt=[0]*2019
cnt[0] = 1
for i in l:
   cnt[i%2019] += 1
import collections
cnt=collections.Counter(cnt).items()
ans=0
for i,j in cnt:
   if i > 1:
      ans+=i*(i-1)//2*j
print(ans)

### FIXED CODE ###

import sys
tmp=sys.stdin.readline().rstrip()
def main():
   ans=0
   cnt=[0]*2019
   cnt[0]+=1
   t=0
   d=1
   for i in reversed(tmp):
      t=(t+int(i)*d)%2019
      cnt[t]+=1
      d=d*10%2019
   for i in cnt:
      ans+=i*(i-1)//2
   print(ans)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

N , K = map(int, input().split())
flag = "F"
while 1:
    if N>100000000*K:
        N -100000000*K
    a = N
    N = abs(N - K)
    

    if a<=K and N <= K:
        if a < N:
            result = a
            flag="T"
        else:
            result = N
            flag="T"
    if flag == "T":
        break
print(result)

### FIXED CODE ###

import math

N , K = map(int, input().split())
flag = "F"
if N !=0:
    while 1:
        lenN = int (math.log10(N) + 1)
        lenK = int (math.log10(K) + 1)
        N = abs(N-K*(10**abs(lenN-lenK-1)))
        lenN = int (math.log10(N) + 1)
        if abs(lenN-lenK)<2:
            break



        
while 1:
    
    
    a = N
    N = abs(N - K)
    

    if a<=K and N <= K:
        if a < N:
            result = a
            flag="T"
        else:
            result = N
            flag="T"
    if flag == "T":
        break
print(result)
### BUGGY CODE ###

import numpy as np
N = int(input())
S = input()

npans = np.zeros(N,dtype = int)
for i,s in enumerate(S):
    if s == 'W':
        npans[i+1:] += 1
    else:
        npans[:i] += 1
print(np.min(npans))


### FIXED CODE ###

import numpy as np
N = int(input())
S = input()

numW = [0]*N
numE = [0]*N
tmpW = 0
tmpE = 0
for i,s in enumerate(S):
    if s == 'W':
        tmpW += 1
    else:
        tmpE += 1

    numW[i] = tmpW
    numE[i] = tmpE

npans = np.zeros(N,dtype = int)
npans[0] = numE[-1] - numE[0]
for i in range(1,N):
    npans[i] = numW[i-1] + numE[-1] - numE[i]
print(np.min(npans))


# npans = np.zeros(N,dtype = int)
# for i,s in enumerate(S):
#     if s == 'W':
#         npans[i+1:] += 1
#     else:
#         npans[:i] += 1
# print(np.min(npans))
### BUGGY CODE ###

def sum_lr(l, r, cnt):
    cnt += 1
    lr = l + r
    if lr < 10:
        l = lr
        return l, cnt
    else:
        l = lr // 10
        r = lr % 10
        return sum_lr(l, r, cnt)

from collections import defaultdict
aaa = defaultdict(lambda:{})
for l in range(10):
    for r in range(10):
        aaa[l][r] = sum_lr(l,r,0)
        

def dc_compression(d, c, ret, cnt):
    if c == 1:
        ret.append((d, 1))
        return ret, cnt
    
    if c % 2 == 1:
        ret.append((d, 1))
        c -= 1
    d, tmp_cnt = aaa[d][d]
    c = c // 2
    cnt += tmp_cnt * c
    #print(d, c, ret, cnt)
    return dc_compression(d, c, ret, cnt)
    
    
    
        

M = int(input())

nums = []
l = 0
cnt = 0
import sys
input = sys.stdin.readline
for _ in range(M):
    d, c = map(int, input().split())
    tmp_nums, tmp_cnt= dc_compression(d,c,[], 0)
    nums += tmp_nums
    cnt += tmp_cnt
    
#print(nums)    
    
for d, c in nums:
    l, tmp_cnt = aaa[l][d]
    cnt += tmp_cnt

print(cnt-1)

### FIXED CODE ###

def sum_lr(l, r, cnt):
    cnt += 1
    lr = l + r
    if lr < 10:
        l = lr
        return l, cnt
    else:
        l = lr // 10
        r = lr % 10
        return sum_lr(l, r, cnt)

from collections import defaultdict
aaa = defaultdict(lambda:{})
for l in range(10):
    for r in range(10):
        aaa[l][r] = sum_lr(l,r,0)
        

def dc_compression(d, c, ret, cnt):
    if c == 1:
        ret.append((d, 1))
        return ret, cnt
    
    if c % 2 == 1:
        ret.append((d, 1))
        c -= 1
    d, tmp_cnt = aaa[d][d]
    c = c // 2
    cnt += tmp_cnt * c
    #print(d, c, ret, cnt)
    return dc_compression(d, c, ret, cnt)
    
    
    
        

M = int(input())

nums = []
l = 0
cnt = 0
import sys
input = sys.stdin.readline
for _ in range(M):
    d, c = map(int, input().split())
    tmp_nums, tmp_cnt= dc_compression(d,c,[], 0)
    for t,_ in tmp_nums:
        nums.append(t)
    
    cnt += tmp_cnt
    
#print(nums)    
    
for d in nums:
    l, tmp_cnt = aaa[l][d]
    cnt += tmp_cnt

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

#-*- coding: utf-8 -*-

n, k = map(int, raw_input().split())
src = []
for i in range(n):
    src.append(map(int, raw_input().split()))
src.sort(key=lambda x:x[0]) # 0番目の要素でソート

data = []
for a, b in src:
    for i in range(b):
        data.append(a)

print data[k-1]

### FIXED CODE ###

#-*- coding: utf-8 -*-

def get_ans():
    n, k = map(int, raw_input().split())
    src = []
    for i in range(n):
        src.append(map(int, raw_input().split()))
    src.sort(key=lambda x:x[0]) # 0番目の要素でソート

    cnt = 0
    for a, b in src:
        cnt = cnt + b
        if cnt >= k:
            return a
            break
    return src[n-1][1]

if __name__ == '__main__':
    print get_ans()
### BUGGY CODE ###

N = int(input())
k = list(map(int, input().split()))
d = {}
dd = {}
for i in range(N):
    if k[i] in d:
        d[k[i]] += 1
    else:
        d[k[i]] = 1
for key in d:
    dd[key] = int(d[key]*(d[key]-1)/2)
for i in range(N):
    res = 0
    for key in d:
        if d[key]>1:
            if key == k[i]:
                res += int((d[key]-1)*(d[key]-2)/2)
            else:
                res += dd[key]
    print(res)

### FIXED CODE ###

N = int(input())
k = list(map(int, input().split()))
d = {}
dd = {}
for i in range(N):
    a = k[i]
    if a in d:
        d[a] += 1
    else:
        d[a] = 1
tot = 0
for key in d:
    a = d[key]
    dd[key] = int(a*(a-1)/2)
    tot += dd[key]
for i in range(N):
    print(tot - d[k[i]]+1)
### BUGGY CODE ###

N = int(input())
# 題意は「1~Nの値iにおいて、Nまでにあるiの倍数の総和を求めよ」ということなので
sum = 0
for i in range(1, N+1):
    k = N // i # k = iの倍数の項数
    sum += int(i * k * (k+1) / 2)
print(sum)


### FIXED CODE ###

N = int(input())
# 題意は「1~Nの値iにおいて、Nまでにあるiの倍数の総和を求めよ」ということなので
sum = 0
for i in range(1, N+1):
    k = N // i # k = iの倍数の項数
    sum += int(i * k * (k+1) / 2)
print(sum)
### BUGGY CODE ###

n = int(input())
s = input()
count = 0
len = len(s)

for i in range(len):
        for j in range(i, len):
            if s[j] != s[i]:
                for k in range(j, len):
                    if s[k] != s[j] and s[k] != s[i] and j - i != k - j:
                        count += 1
print(count)

### FIXED CODE ###

import math

n = int(input())
s = input()
count = 0

rCount = s.count("R")
gCount = s.count("G")
bCount = s.count("B")
ans = rCount * gCount * bCount

for dis in range(1, math.ceil(len(s) / 2)):
    for i in range(dis, len(s) - dis):
        if s[i-dis] != s[i] and s[i-dis] != s[i+dis] and s[i] != s[i+dis]:
            ans -= 1
print(ans)
### BUGGY CODE ###

import numpy as np
#n,m=map(int,input().split())
#r=np.array([list(map(int,input().split())) for _ in range(m)])
n, m, *r = map(int, open(0).read().split())
r = np.array(r).reshape(-1,2)
#n,m=10**1,10**1-1
#r=np.array([[i+1,i+2] for i in range(m)])

start=np.array([1], dtype='int64')
done=np.array([1], dtype='int64')
ans=np.array([-1]*n, dtype='int64')

for _ in range(n-1):
    start_tmp=np.array([], dtype='int64')
    for st in start:
        #print(st)
        r_st = r[np.any(r==st, axis=1)].flatten()
        r_gl = np.setdiff1d(np.delete(r_st, np.where(r_st == st)), done)
        
        start_tmp=np.unique(np.append(start_tmp, r_gl))
        done=np.unique(np.append(done, r_gl))
        #print(r_gl)
        ans[r_gl-1] = st
        
    start = start_tmp
    #print(ans)
    #print(start, done)
    
    if len(done)==n:
        break
    
print('Yes')
print('\n'.join(map(str, ans[1:])))

### FIXED CODE ###

print('Yes')

from collections import deque  

n, m = map(int, input().split())
graph = [[] for _ in range(n+1)]

for i in range(m):
    a, b = map(int, input().split())
    graph[a].append(b)
    graph[b].append(a)
#print(graph)

ans = [-1] * (n+1)
ans[0] = 0
ans[1] = 0

d = deque()
d.append(1)

while d:
    v = d.popleft()
    for i in graph[v]:
        if ans[i] != -1:
            continue
        ans[i] = v
        d.append(i)

print(*ans[2:], sep="\n")
### BUGGY CODE ###

import math

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

ans = 0
mod = 10 ** 9 + 7

def combinations_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

for i in range(1,n+1):
    if i != a and i != b:
        ans += combinations_count(n,i)

print(ans%mod)

### FIXED CODE ###

n,a,b=map(int,input().split())
mod=10**9+7
def combination(p,k):
    a,b=1,1  
    for i in range(k):
        a*=(p-i)
        a%=mod
        b*=(i+1)
        b%=mod
    return (a*pow(b,mod-2,mod))%mod
print((pow(2,n,mod)-1-combination(n,a)-combination(n,b))%mod)
### BUGGY CODE ###

inf = 10**20
n, k = map(int, input().split())
hs = [int(s) for s in input().split()]

dp = [inf] * n
dp[0] = 0

for i in range(1, n):
    for j in range(i-1, max(0, i-k)-1, -1):
        dp[i] = min(dp[j] + abs(hs[i] - hs[j]), dp[i])
print(dp[-1])

### FIXED CODE ###

inf = 10**20
n, k = map(int, input().split())
hs = [int(s) for s in input().split()]
 
dp = [inf] * n
dp[0] = 0
 
for i in range(1, n):
    for j in range(i-1, max(0, i-k)-1, -1):
        dp[i] = min(dp[j] + abs(hs[i] - hs[j]), dp[i])
print(dp[-1])
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
from bisect import bisect_left,bisect
def main():
    h, w, m = map(int,input().split()) 
    h_lis = [0] * h
    w_lis = [0] * w
    hw_lis = [[] for i in range(h)] 
    for i in range(m):
        hh, ww = map(int,input().split())
        hh -= 1
        ww -= 1
        h_lis[hh] += 1
        w_lis[ww] += 1
        hw_lis[hh].append(ww)
    h_max_index = [i for i, h in enumerate(h_lis) if h == max(h_lis)]
    w_max_index = [i for i, w in enumerate(w_lis) if w == max(w_lis)]
    for h_i in h_max_index:
        hw_lis[h_i].sort()
        for w_i in w_max_index:
            if bisect_left(hw_lis[h_i], w_i) == bisect(hw_lis[h_i], w_i):
                print(h_lis[h_i] + w_lis[w_i])
                sys.exit()
    else:
        print(h_lis[h_i] + w_lis[w_i] - 1)

if __name__=='__main__':
    main()

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
from bisect import bisect_left,bisect
def main():
    h, w, m = map(int,input().split()) 
    h_lis = [0] * (h+1)
    w_lis = [0] * (w+1)
    bombs = set([tuple(map(int,input().split())) for i in range(m)])
    for hh, ww in bombs:
        h_lis[hh] += 1
        w_lis[ww] += 1
    max_h = max(h_lis)
    max_w = max(w_lis)
    h_max_index = [i for i, h in enumerate(h_lis) if h == max_h]
    w_max_index = [i for i, w in enumerate(w_lis) if w == max_w]
    for h_i in h_max_index:
        for w_i in w_max_index:
            if not (h_i, w_i) in bombs:
                print(h_lis[h_i] + w_lis[w_i])
                sys.exit()
    else:
        print(h_lis[h_i] + w_lis[w_i] - 1)

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

n, k = list(map(int, input().split()))
P = list(map(int, input().split()))

dp = [0] * n
m = {}

def func(x):
    return m.get(x, sum(range(x+1)) / x)
    #return sum(range(x+1)) / x

for i in range(n):
    if i - k >= 0:
        dp[i] = dp[i - 1] - func(P[i - k]) + func(P[i])
    else:        
        dp[i] = sum([func(p) for p in P[:i + 1]])

print(max(dp))

### FIXED CODE ###

n, k = list(map(int, input().split()))
P = list(map(int, input().split()))

dp = [0] * n
m = {}

def func(x):
    return m.get(x, sum(range(x+1)) / x)
    #return sum(range(x+1)) / x

for i in range(n):
    if i - k >= 0:
        dp[i] = dp[i - 1] - func(P[i - k]) + func(P[i])
    else:
        dp[i] += func(P[i]) + dp[i-1]

print(max(dp))
### BUGGY CODE ###

#!/usr/bin/python3
# abc061_c
"""
Big Array
"""

test = False

def answer():
    """
    答えを出力する関数
    """
    l_1 = []
    l_2 = []
    N, K = map(int, input().split())

    for _ in range(N):
        l_1.append(list(map(int, input().split())))


    l_1.sort()
    if test:
        print(l_1)

    for v in l_1:
        l_2.extend([v[0]] * v[1])

    # 小さい順にソートして、K-1番目の要素を出力
    if test:
        print(l_2)
    print(l_2[K-1])


def main():
    """
    処理を実行する関数
    """
    answer()


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/python3
# abc061_c
"""
Big Array
"""

def answer():
    """
    答えを出力する関数
    """
    l = []
    N, K = map(int, input().split())
    counter = 0

    for _ in range(N):
        l.append(list(map(int, input().split())))

    l.sort()
    for v in l:
        counter += v[1]
        if counter >= K:
            print(v[0])
            break

def main():
    """
    処理を実行する関数
    """
    answer()


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

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

mod=10**9+7

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


### FIXED CODE ###

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

mod = 10 ** 9 + 7

sum_a=0
for i in A:
    sum_a+=i
    sum_a%=mod

total=0
for i in range(N - 1):
    sum_a -= A[i]
    total+=A[i]*(sum_a)
    total%=mod
print(total)
### BUGGY CODE ###

from collections import deque
def main():
    h,w=map(int,input().split())
    maze=[]
    r_append=maze.append
    for i in range(h):
        #r_append=maze.append
        row=input()
        r_append(row)
    #print(maze)
    #root=[[-1 for i in range(h*w)] for i in range(h*w)]
    root=[0]*(h*w)
    for i in range(h*w):
        root[i]=[-1]*(h*w)
    ina=[i for i in range(h*w)]
    for i in range(h):
        for j in range(w):
        # print(maze[i][j])
            now=w*i+j
            hidari=w*i+j-1
            migi=w*i+j+1
            ue=w*(i-1)+j
            sita=w*(i+1)+j
            if maze[i][j]==".":
                if j>0:
                    if maze[i][j-1]!="#":
                        root[now][hidari]=0
                if i+1<h:
                    if maze[i+1][j]!="#":
                        root[now][sita]=0
                if j+1<w:
                    if maze[i][j+1]!="#":
                        root[now][migi]=0
                if 0<i:
                    if maze[i-1][j]!="#":
                        root[now][ue]=0
            else:
                ina[now]=-1
                if j>0:
                    root[now][hidari]=-1
                if i+1<h:
                    root[now][sita]=-1
                if j+1<w:
                    root[now][migi]=-1
                if 0<i:
                    root[now][ue]=-1
    #print(root)
    max=0
    hw=h*w
    for start in range(hw):
        if ina[start]==-1:
           # print(start,"is unreachable")
            continue
        dist=[0]*(hw)
        now=start
        dist[start]=0
        visted=[0]*(hw)
        toVis=deque()
        visted[now]=1
        for i in range(hw):
            if root[now][i]!=-1:
                toVis.append(i)
                dist[i]=dist[now]+1
        while len(toVis)>0:
            now=toVis.popleft()
            visted[now]=1
            le=dist[now]
            for i in range(hw):
                if root[now][i]!=-1 and visted[i]!=1:
                    toVis.append(i)
                    dist[i]=le+1
        farest=dist[now]
        if max<farest:
            max=farest
    print(max)
            
if __name__=="__main__":
    main()


    

### FIXED CODE ###

h,w=map(int,input().split())
n=h*w
inf=10**6
field=[]
for i in range(h):
    field.append(input())
dist=[[inf]*n for i in range(n)]
for i in range(h):
    for j in range(w):
        if field[i][j]=="#":continue
        if j+1<w and field[i][j+1]!="#":
            dist[i*w+j][i*w+j+1]=1
            dist[i*w+j+1][i*w+j]=1
        if i+1<h and field[i+1][j]!="#":
            dist[i*w+j][(i+1)*w+j]=1
            dist[(i+1)*w+j][i*w+j]=1
for i in range(n):
    for j in range(n):
        for k in range(n):
            dist[j][k]=min(dist[j][k],dist[j][i]+dist[i][k])
ans=0
for i in range(n):
    for j in range(n):
        if i==j:
            continue
        if dist[i][j]==inf:
            continue
        ans=max(ans,dist[i][j])
print(ans)
### BUGGY CODE ###

N,M=map(int,input().split())
A=list(map(int,input().split()))
for i in range(M):
    A[A.index(max(A))] = max(A)//2


print(sum(A))


### FIXED CODE ###

#from operator import itemgetter
#from collections import Counter
import heapq
#N = int(input())
N, M = map(int, input().split())
A = list(map(lambda x: int(x)*(-1), input().split()))
#A = [int(input()) for i in range(N)]

heapq.heapify(A)

for i in range(M):
    max = heapq.heappop(A)
    heapq.heappush(A, max*(-1)//2*(-1))
print(-sum(A))
### BUGGY CODE ###

def divisor(n):
    cnt = 1
    for i in range(1,int(n**0.5)+1):
        if n % i == 0:
            cnt += 1
    return cnt


N = int(input())
lis = [0] * (10**7+1)
lis[1] = 1
#print(divisor(N))
for i in range(2,10**7):
    if lis[i] != 0:
        continue
    val = divisor(i)
    for j in range(1,100):
        if i ** j > int(1e7):
            break
        lis[i**j] = val + j-1

ans = 0
for i in range(1,N+1):
    ans += i*lis[i]
print(ans)


### FIXED CODE ###

N = int(input())
lis = [1] * (10**7+1)
for i in range(2,10**7+1):
    for j in range(i,10**7+1,i):
        lis[j] += 1
ans = 0
for i in range(1,N+1):
    ans += lis[i] * i
print(ans)