Harryxun/stf_run huggingface dataset:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import collections
import itertools
import numpy


def main():
  h, w, _ = map(int, input().split())
  values = numpy.array([[int(v == '#') for v in input().strip()] for _ in range(h)])
  flags = numpy.zeros_like(values)
  areas = []

  for y, x in itertools.product(range(h), range(w)):
    if values[y][x] == 1:
      flags[y][x] = 1
      areas.append([x, y, x, y])

  for area in areas:
    sx, sy, ex, ey = area

    while True:
      if sx > 0 and numpy.sum(flags[sy:ey + 1, sx - 1]) == 0:
        flags[sy:ey + 1, sx - 1] += 1
        sx -= 1
      elif sy > 0 and numpy.sum(flags[sy - 1, sx:ex + 1]) == 0:
        flags[sy - 1, sx:ex + 1] += 1
        sy -= 1
      elif ex + 1 < w and numpy.sum(flags[sy:ey + 1, ex + 1]) == 0:
        flags[sy:ey + 1, ex + 1] += 1
        ex += 1
      elif ey + 1 < h and numpy.sum(flags[ey + 1, sx:ex + 1]) == 0:
        flags[ey + 1, sx:ex + 1] += 1
        ey += 1
      else:
        break

    area[0], area[1], area[2], area[3] = sx, sy, ex, ey

  rets = numpy.zeros_like(values)

  for i, (sx, sy, ex, ey) in enumerate(areas, start=1):
    for x, y in itertools.product(range(sx, ex + 1), range(sy, ey + 1)):
      rets[y, x] = i

  for r in rets:
    print(' '.join(map(str, r)))


if __name__ == '__main__':
  main()


### FIXED CODE ###

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


def main():
  h, w, _ = map(int, input().split())
  values = [[int(v == '#') for v in input().strip()] for _ in range(h)]
  flags = [[0] * w for _ in range(h)]
  areas = []

  for y, x in itertools.product(range(h), range(w)):
    if values[y][x] == 1:
      flags[y][x] = 1
      areas.append([x, y, x + 1, y + 1])

  for area in areas:
    sx, sy, ex, ey = area

    while True:
      if sx > 0 and sum(flags[y][sx - 1] for y in range(sy, ey)) == 0:
        for y in range(sy, ey):
          flags[y][sx - 1] += 1
        sx -= 1
      elif sy > 0 and sum(flags[sy - 1][x] for x in range(sx, ex)) == 0:
        for x in range(sx, ex):
          flags[sy - 1][x] += 1
        sy -= 1
      elif ex < w and sum(flags[y][ex] for y in range(sy, ey)) == 0:
        for y in range(sy, ey):
          flags[y][ex] += 1
        ex += 1
      elif ey < h and sum(flags[ey][x] for x in range(sx, ex)) == 0:
        for x in range(sx, ex):
          flags[ey][x] += 1
        ey += 1
      else:
        break

    area[0], area[1], area[2], area[3] = sx, sy, ex, ey

  rets = [[0] * w for _ in range(h)]

  for i, (sx, sy, ex, ey) in enumerate(areas, start=1):
    for x, y in itertools.product(range(sx, ex), range(sy, ey)):
      rets[y][x] = i

  for r in rets:
    print(' '.join(map(str, r)))


if __name__ == '__main__':
  main()
#encoding:utf-8

import numpy as np
# import sys
# sys.setrecursionlimit(1000000)

H, W = map(int, input().split())
S = []
for i in range(H):
    s = list(input())
    S.append(s)

S_ = np.array(S)

def count_answer(x,y,num_b,num_w):
    # print(used)
    # global num_b,num_w
    if S_[x][y] == "#":
        num_b += 1
    else:
        num_w += 1
    used[x][y] = 1
    dx = [0,0,1,-1]
    dy = [1,-1,0,0]
    # print("x,y:",x,y)
    for i in range(4):
        next_x = x + dx[i]
        next_y = y + dy[i]
        # print(next_x,next_y)
        if next_x == -1 or next_y == -1 or next_x >= H or next_y >= W:
            pass
        elif used[next_x,next_y] == 1:
            pass
        elif S_[next_x][next_y] != S_[x][y]:
            num_b,num_w = count_answer(next_x,next_y,num_b,num_w)
    return num_b,num_w

answer = 0
used = np.zeros((H,W))
for i in range(H):
    for j in range(W):
        if used[i][j] == 1:
            continue
        num_b = 0
        num_w = 0
        if S_[i,j] == "#":
            num_b,num_w  = count_answer(i,j,num_b,num_w)
            answer += num_b*num_w
print(answer)


### FIXED CODE ###

#encoding:utf-8

import numpy as np
import sys
sys.setrecursionlimit(1000000)

H, W = map(int, input().split())
S = []
for i in range(H):
    s = list(input())
    S.append(s)


def count_answer(x,y,num_b,num_w):
    # print(used)

    if S[x][y] == "#":
        num_b += 1
    else:
        num_w += 1
    used[x][y] = 1
    dx = [0,0,1,-1]
    dy = [1,-1,0,0]
    # print("x,y:",x,y)
    for i in range(4):
        next_x = x + dx[i]
        next_y = y + dy[i]
        # print(next_x,next_y)
        if next_x == -1 or next_y == -1 or next_x >= H or next_y >= W:
            pass
        elif used[next_x,next_y] == 1:
            pass
        elif S[next_x][next_y] != S[x][y]:
            num_b,num_w = count_answer(next_x,next_y,num_b,num_w)
    return num_b,num_w

answer = 0
used = np.zeros((H,W))
for i in range(H):
    for j in range(W):
        if used[i][j] == 1:
            continue
        num_b = 0
        num_w = 0
        if S[i][j] == "#":
            num_b,num_w  = count_answer(i,j,num_b,num_w)
            answer += num_b*num_w
print(answer)
import fractions

N = int(input())
inp_ints = list(map(int, input().split()))
ints = list(set(inp_ints))
""" uniq_ints = list(set(inp_ints))

ints = uniq_ints
for m in uniq_ints:
    if inp_ints.count(m) >= 2:
        ints.append(m) """

gcd = 0
result = 1
for i in range(len(ints)):
    gcd = 0
    for m in ints[:i]:
        gcd = fractions.gcd(gcd, m)
    for m in ints[i+1:]:
        gcd = fractions.gcd(gcd, m)
    if gcd > result:
        result = gcd

print(result)

### FIXED CODE ###

A, B, T = map(int, input().split())
result = T // A * B

print(result)
m=float("INF")
sunukes=[]
for i in range(2,-1,-1):
    for j in range(100,10,-1):
        #print(i,j)
        sunuke=j*(10**i)-1
        s=str(sunuke)
        sn=0
        for k in range(len(s)):
            sn+=int(s[k])
        x=sunuke/sn
        #print(sn,x,i,j,j*10**i-1)
        if x<=m :
            m=x
            sunukes.append(sunuke)
for i in range(9,0,-1):
    sunukes.append(i)
k=int(input())
#print(sunukes)
print(sunukes[-k])


### FIXED CODE ###

m=float("INF")
sunukes=[]
for i in range(7,-1,-1):
    for j in range(1000,10,-1):
        #print(i,j)
        sunuke=j*(100**i)-1
        s=str(sunuke)
        sn=0
        for k in range(len(s)):
            sn+=int(s[k])
        x=sunuke/sn
        #print(sunuke,x)
        if x<=m :
            m=x
            sunukes.append(sunuke)
for i in range(9,0,-1):
    sunukes.append(i)
sunukes=sunukes[::-1]
k=int(input())
#print(sunukes)
for i in range(k):
    print(sunukes[i])
s = input()
print(700　+ 100*s.count('o'))

### FIXED CODE ###

s=input()
print(700+int(s.count("o"))*100)
import sys
input = sys.stdin.readline

N, K = map(int, input().split())
A = [int(input() for _ in range(N))]
## 種類数の求め方
# 1. A内の要素を取り出して、それがA内に存在するとき：種類＋１
# 2. その要素を重複数だけAから削除してループ

kinds = 0
A = sorted(A)
duplicatedList = []
while len(A) > 0:
    if A[0] in A:
        kinds += 1
        duplicatedList.append(A.count(A[0]))
        for j in range(A.count(A[0])):
            A.remove(A[0])

if kinds <= K:
    print('0')
elif kinds > K:
    duplicatedList = sorted(duplicatedList)
    tmp = 0
    for i in range(kinds-K):
        tmp += duplicatedList[i]
    print(tmp)

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
d={}
l=[]
for i in range(n):
    try:
        l[d[a[i]]]+=1
    except:
        d[a[i]]=len(l)
        l.append(1)
ans=0
l.sort()
for i in range(len(l)-k):
    ans+=l[i]
print(ans)
from itertools import accumulate
n,k = map(int,input().split())
p = list(map(int,input().split()))

P = []+p
P = list(accumulate(P))

ans = []

if n == 1:
    print((p[0]+1)/2)
else:    
    for i in range(n-k):
        ans.append(P[i+k]-P[i])
    print((max(ans)+k)/2)

### FIXED CODE ###

from itertools import accumulate
n,k = map(int,input().split())
p = list(map(int,input().split()))

P = []+p
P = list(accumulate(P))

ans = []

if n == 1:
    print((p[0]+1)/2)
elif n == k:
    print((sum(p)+n)/2)
else:    
    for i in range(n-k):
        ans.append(P[i+k]-P[i])
    print((max(ans)+k)/2)
# 帰宅経路数と時間を取得
N, T = map(int, input().split())
# 時間制限
ans = 1001
# 制約判断
if N < 1 or N > 100 or T < 1 or T > 1000:
    SystemExit
# N個の帰宅経路と時間を取得し、比較する
for i in range(N):
    cost, time = map(int, input().split())
    if time < T:
        ans = min(ans, cost)
# 出力する
if ans == 1001:
    print("TLE")
else:
    print(ans)

### FIXED CODE ###

#年齢を取得
N = int(input())
#年齢による条件判断
if N == 1:
    print('Hello World')
elif N == 2:
    #AとBの値を取得
    A = int(input())
    B = int(input())
    #制約の判断
    if A < 1 or A > 9 or B < 1 or B > 9:
        SystemExit
    print(A+B)
s = input()
if(s[1] == "R"):
  print("ABC")
 else:
  print("ARC")
  

### FIXED CODE ###

s = input()
if(s[1] == "R"):
  print("ABC")
else:
  print("ARC")
N = input()  #一応読むけど、ループ回せば不要では
aList=input().split()


opCnt = 0
isAllE = True  #奇数見つかるまでは見なしTrue

while isAllE
  for a in aList:
    if a%2 == 1:
      isAllE = False
  else:
    opCnt = opCnt + 1

print(opCnt)

### FIXED CODE ###

N = input()  #一応読むけど、ループ回せば不要では
aList=input().split()

opCnt = 0
isAllE = True  #奇数見つかるまでは見なしTrue

while isAllE:
  for a in aList:
    if int(a)%2 == 1:
      isAllE = False
      break
  else:
    opCnt = opCnt + 1
    for i,a in enumerate(aList):
      aList[i] = int(int(a)/2)

print(opCnt)
import sys
sys.setrecursionlimit(10 ** 6)
N, K = map(int, input().split())
S = list(map(int, list(input())))
def solve(l, k):
  if k == K:
    temp = 1
    thrbl = 0
    for i in range(l + 1, N):
      temp += 1
      if thrbl == 0 and S[i] == 1:
        thrbl = 1
      elif thrbl == 1 and S[i] == 0:
        temp -= 1
        break
    #print(l, temp, k)
    return temp
  temp = 0
  for i in range(l + 1, N):
    if S[i] == 0:
      temp = solve(i, k + 1)
      thrbl = 0
      for j in range(l + 1, i):
        temp += 1
        if thrbl == 0 and S[j] == 1:
          thrbl = 1
        elif thrbl == 1 and S[j] == 0:
          temp -= 1
          break
      if k == 1:
        thrbl = 0
        for j in range(l, -1, -1):
          temp += 1
          #print(j)
          if j == l:
            continue
          if thrbl == 0 and S[j] == 1:
            thrbl = 1
          elif thrbl == 1 and S[j] == 0:
            temp -= 1
            break
      #print(l, i, temp, k)
      return temp
res = 0
for i in range(N):
  if S[i] == 0:
    if i > 0 and S[i - 1] != 0:
      res = max(solve(i, 1), res)
    elif i == 0:
      res = max(solve(i, 1), res)
print(res) if res != 0 else print(N)

### FIXED CODE ###

N, K = map(int, input().split())
S = list(input()) + [-1]
bw = [0] * N
ind = 0
for i in range(N):
  bw[ind] += S[i] == S[i + 1]
  if S[i] != S[i + 1]:
    bw[ind] += 1
    ind += 1
ind = 0
res = 0
cumsumbw = [0] + [bw[0]] + [0] * (N - 1)
for i in range(1, N):
  cumsumbw[i + 1] = cumsumbw[i] + bw[i]
if N - 2 * K <= 0:
  print(N)
  exit(0)
for i in range(N - 2 * K):
  if S[cumsumbw[i]] == "1":
    res = max(res, cumsumbw[i + 2 * K + 1] - cumsumbw[i])
  else:
    res = max(res, cumsumbw[i + 2 * K] - cumsumbw[i])
  #print(res)
print(res)
#print(bw)
#print(cumsumbw)
a,b,c = map(int, raw_input().split)

count=0
for x in range(a,b+1):
    if  c%x == 0:
       count += 1
print(str(count))     
       
  

### FIXED CODE ###

a,b,c = map(int, raw_input().split())

count=0
for x in range(a,b+1):
    if  c%x == 0:
       count += 1
print(count)
from heapq import heappop, heappush
ab = lambda a,b:abs(a-b)
area = lambda a,b:ab(a[1],b[1])*ab(a[0],b[0])
dist = lambda a,b:(ab(a[1],b[1])**2+ab(a[0],b[0])**2)

N, K = map(int, input().split())
A = []
graph = []
inf = float('INF')
mn_x, mn_y, mx_x, mx_y = inf, inf, 0, 0
for i in range(N):
    a,b = map(int, input().split())
    A.append([a,b])
    graph.append([inf for i in range(N)])
    mn_x, mn_y, mx_x, mx_y = min(mn_x, a), min(mn_y, b), max(mx_x, a), max(mx_y, b)

if N == 2:
    print(area(a,b))
    exit()
center = [(mx_x - mn_x) / 2, (mx_y - mn_y) / 2]
mn_dist = inf
for i in range(N):
    for j in range(N):
        if i == j:
            continue
        graph[i][j] = graph[j][i] = dist(A[i], A[j]) + dist(A[j], center)
        if mn_dist > graph[i][j]:
            mn_dist = graph[i][j]
            mn_dict = {i:1,j:1}
            mn_lst = [i,j]

x_lst = [A[mn_lst[0]][0], A[mn_lst[1]][0]]
y_lst = [A[mn_lst[0]][1], A[mn_lst[1]][1]]
cands = []
tmp = min([[graph[mn_lst[0]][i], i] for i in range(N) if i not in mn_dict])
heappush(cands, tmp)
tmp = min([[graph[mn_lst[1]][i], i] for i in range(N) if i not in mn_dict])
heappush(cands, tmp)
    
for i in range(K-2):
    _, idx = heappop(cands)
    mn_dict[idx] = 1
    mn_lst.append(idx)
    x_lst.append(A[idx][0])
    y_lst.append(A[idx][1])
    # print(idx, mn_lst, graph[3][3])
    tmp_lst = [[graph[idx][i], i] for i in range(N) if i not in mn_dict]
    if tmp_lst != []:
        tmp = min(tmp_lst)
        heappush(cands, tmp)

a = [min(x_lst), min(y_lst)]
b = [max(x_lst), max(y_lst)]
print(area(a,b))
# for i in range(N):
#     print(graph[i])
# print(a,b, cands)


### FIXED CODE ###

ab = lambda a,b:abs(a-b)
area = lambda a,b:ab(a[1],b[1])*ab(a[0],b[0])

N, K = map(int, input().split())
A = []
x_lst = []
y_lst = []
for i in range(N):
    a,b = map(int, input().split())
    A.append([a,b])
    x_lst.append(a)
    y_lst.append(b)

x_lst.sort()
y_lst.sort()
mn = float('INF')
for x in range(N-1):
    for x_ in range(x,N):
        for y in range(N-1):
            for y_ in range(y,N):
                cnt = 0
                for a,b in A:
                    if x_lst[x] <= a <= x_lst[x_] and y_lst[y] <= b <= y_lst[y_]:
                        cnt += 1
                if cnt >= K:
                    mn = min(mn, area([x_lst[x],y_lst[y]], [x_lst[x_], y_lst[y_]]))
print(mn)
n=int(input())
d=list(map(int,input().split()))
d.sort()
print(d[n//2]-d[n//
   

### FIXED CODE ###

n=int(input())
d=list(map(int,input().split()))
d.sort()
print(d[n//2]-d[n//2-1])
s = input()
x,y = map(int,input().split())
 
X = []
Y = []
flag = 0
tmp = 0
for i in s:
    if i == "T":
        if flag == 0:
            if tmp != 0:
                X.append(tmp)
            flag = 1
            tmp = 0
        else:
            if tmp != 0:
                Y.append(tmp)
            flag = 0
            tmp = 0
    else:
        tmp += 1
if tmp != 0:
    if flag == 0:
        X.append(tmp)
    else:
        Y.append(tmp)

if s[0] !="T":
    tmpX = X[0]
    del X[0]
else:
    tmpX = 0

X = sorted(X)
Y = sorted(Y)
sumX = sum(X)
sumY = sum(Y)
tmpY = 0
 
ans = 0
 
if (x+sumX-tmpX)%2 == 1:
    ans = 1
else:
    mokuhyoX = (x+sumX-tmpX)//2
if (y+sumY-tmpY)%2 == 1:
    ans = 1
else:
    mokuhyoY = (y+sumY-tmpY)//2
if mokuhyoX < 0 or mokuhyoY < 0:
    ans = 1

# mokuhyoX
if ans == 0:
    dpX = [[False]*(mokuhyoX+1) for _ in range(len(X)+1)]
    dpX[0][0] = True
    for i in range(len(X)):
        for j in range(mokuhyoX+1):
            dpX[i+1][j] = dpX[i+1][j] or dpX[i][j]
            if j >= X[i]:
                dpX[i+1][j] = dpX[i+1][j] or dpX[i][j-X[i]]
    
    
# mokuhyoY
if ans == 0:
    dpY = [[False]*(mokuhyoY+1) for _ in range(len(Y)+1)]
    dpY[0][0] = True
    for i in range(len(Y)):
        for j in range(mokuhyoY+1):
            dpY[i+1][j] = dpY[i+1][j] or dpY[i][j]
            if j >= Y[i]:
                dpY[i+1][j] = dpY[i+1][j] or dpY[i][j-Y[i]]
 
if ans==0:
    if dpX[len(X)][mokuhyoX] == dpY[len(Y)][mokuhyoY] == True:
        ans = 0
    else:
        ans = 1
    
if ans == 1:
    print("No")
else:
    print("Yes")

### FIXED CODE ###

s = input()
x,y = map(int,input().split())
 
X = []
Y = []
flag = 0
tmp = 0
for i in s:
    if i == "T":
        if flag == 0:
            if tmp != 0:
                X.append(tmp)
            flag = 1
            tmp = 0
        else:
            if tmp != 0:
                Y.append(tmp)
            flag = 0
            tmp = 0
    else:
        tmp += 1
if tmp != 0:
    if flag == 0:
        X.append(tmp)
    else:
        Y.append(tmp)

if s[0] !="T":
    tmpX = X[0]
    del X[0]
else:
    tmpX = 0

X = sorted(X)
Y = sorted(Y)
sumX = sum(X)
sumY = sum(Y)
tmpY = 0
 
ans = 0
 
if (x+sumX-tmpX)%2 == 1:
    ans = 1
else:
    mokuhyoX = (x+sumX-tmpX)//2
if (y+sumY-tmpY)%2 == 1:
    ans = 1
else:
    mokuhyoY = (y+sumY-tmpY)//2
if ans == 0:
	if mokuhyoX < 0 or mokuhyoY < 0:
	    ans = 1

# mokuhyoX
if ans == 0:
    dpX = [[False]*(mokuhyoX+1) for _ in range(len(X)+1)]
    dpX[0][0] = True
    for i in range(len(X)):
        for j in range(mokuhyoX+1):
            dpX[i+1][j] = dpX[i+1][j] or dpX[i][j]
            if j >= X[i]:
                dpX[i+1][j] = dpX[i+1][j] or dpX[i][j-X[i]]
    
    
# mokuhyoY
if ans == 0:
    dpY = [[False]*(mokuhyoY+1) for _ in range(len(Y)+1)]
    dpY[0][0] = True
    for i in range(len(Y)):
        for j in range(mokuhyoY+1):
            dpY[i+1][j] = dpY[i+1][j] or dpY[i][j]
            if j >= Y[i]:
                dpY[i+1][j] = dpY[i+1][j] or dpY[i][j-Y[i]]
 
if ans==0:
    if dpX[len(X)][mokuhyoX] == dpY[len(Y)][mokuhyoY] == True:
        ans = 0
    else:
        ans = 1
    
if ans == 1:
    print("No")
else:
    print("Yes")
n=int(input())

for i in range(26):
  for j in range(15):
    if 4*i+7*j=n:
      print("Yes")
    else:
      print("No")

### FIXED CODE ###

n=int(input())

s="No"
for i in range(26):
  for j in range(15):
    if 4*i+7*j==n:
      s="Yes"
print(s)
n = int(print())
group = 0
if n%3==0:
    group = n/3
elif n%3==1:
    group = (n-1)/3
else:
    group = (n-2)/3
print(int(group))

### FIXED CODE ###

n = int(input())
group = 0
if n%3==0:
    group = n/3
elif n%3==1:
    group = (n-1)/3
else:
    group = (n-2)/3
print(int(group))
ss=['A','G','C','T']
s=list(input())
ans=0
for i in range(len(s)-1):
  if s[i] in ss:
    j=i
    cnt=0
    while s[j] in ss:
      j+=1
      cnt+=1
      
    ans=max(ans,cnt)
      
print(ans)

### FIXED CODE ###

ss=['A','G','C','T']
s=list(input())
ans=0
for i in range(len(s)):
  if s[i] in ss:
    j=i
    cnt=0
    while j<len(s):
      if s[j] in ss:
        cnt+=1
        j+=1
      else:
        break
      
    ans=max(ans,cnt)
      
print(ans)
word=raw_input()
sen=[]
ct=0
while 1:
    sen=map(str,raw_input().split(" "))
    if sen[-1:0]=="END_OF_TEXT":
        break
    else:continue
for i in sen:
    i.lower()
    if i==word:
        ct+=1
    else:continue
print(ct)

### FIXED CODE ###

w=raw_input()
ct=0
while 1:
    s=raw_input()
    if s=='END_OF_TEXT':
        break
    s=s.split()
    for i in s:
        if i.lower()==w :
            ct+=1
print(ct)
from heapq import heappop, heappush, heapify


def heapq_dijkstra(cost, num_v, start):
    """
    ダイクストラ法
    :param cost: 隣接行列
    :param num_v: 頂点数
    :param start: 始点
    :return:
    """
    inf = 10**5
    dist = [(inf if i != start - 1 else 0, i) for i in range(num_v)]
    heapify(dist)
    result = [inf] * num_v
    while dist:
        c, v = heappop(dist)
        next_dist = []
        for f_c, i in dist:
            f_c = min(f_c, c + cost[v][i])
            heappush(next_dist, (f_c, i))
        result[v] = c
        dist = next_dist

    return result


def dijkstra(cost, num_v, start):
    """
    ダイクストラ法
    :param cost: 隣接行列
    :param num_v: 頂点数
    :param start: 始点
    :return:
    """
    inf = float("inf")
    dist = [inf] * num_v
    used = [False] * num_v
    dist[start - 1] = 0
    while True:
        v = -1
        for i in range(num_v):
            if (not used[i]) and (v == -1):
                v = i
            elif (not used[i]) and (dist[i] < dist[v]):
                v = i
        if v == -1:
            break
        used[v] = True

        for i in range(num_v):
            dist[i] = min(dist[i], dist[v] + cost[v][i])
    return dist


def abc035_d():
    n, m, t = map(int, input().split())
    *a, = map(int, input().split())
    inf = float("inf")
    go_cost = [[inf] * n for _ in range(n)]
    re_cost = [[inf] * n for _ in range(n)]
    for _ in range(m):
        f_, t_, c = map(int, input().split())
        go_cost[f_ - 1][t_ - 1] = c
        re_cost[t_ - 1][f_ - 1] = c

    go_route = heapq_dijkstra(go_cost, n, 1)
    re_route = heapq_dijkstra(re_cost, n, 1)
    ans = [_a * (t - go_route[i] - re_route[i]) for i, _a in enumerate(a)]
    print(max(ans))


if __name__ == '__main__':
    abc035_d()


### FIXED CODE ###

def p_d():
    from sys import stdin
    input = stdin.readline
    import sys
    sys.setrecursionlimit(10 ** 6)
    n = int(input())
    route = [[] for _ in range(n)]
    for _ in range(n - 1):
        u, v, w = map(int, input().split())
        w = 0 if w & 1 == 0 else 1
        route[u - 1].append((v - 1, w))
        route[v - 1].append((u - 1, w))

    ans = [-1] * n

    def dfs(p, d):
        ans[p] = d
        for i, j in route[p]:
            if ans[i] < 0:
                dfs(i, d ^ j)

    dfs(0, 0)
    print("\n".join(map(str, ans)))
    
p_d()
N, K = map(int, input().split())
Dices = list(map(int, input().split()))
Que = []
Eyes = {}
for i in range(K):
    Que.append(Dices[i])
for i in range(K, N):
    Eyes[i] = sum(Que)
    Que.pop(0)
    Que.append(Dices[i])
a = 0
b = 0
for k, v in Eyes.items():
    if v > a:
        a = v
        b = k
ans = 0
for i in range(k-K+1, k+1):
    ans += (Dices[i]+1)/2
print(ans)

### FIXED CODE ###

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

exv = [(e+1)/2 for e in dices]
temp = sum(exv[0:K])
result = temp
for i in range(N-K):
    temp -= exv[i]
    temp += exv[i+K]
    if temp > result:
        result = temp
print(result)
n, k = map(int, input().split())
s = input()
hand_list = []
for i in range(n):
    if i == 0:
        hand_list.append(i)
    else:
        if s[i] != s[i - 1]:
            hand_list.append(i)
hand_list.append(n)

ans_list = []
if len(hand_list) > 2 * k:
    for i in range(len(hand_list) - 2 * k):
        if s[i] == '1':
            ans = hand_list[i + 2 * k + 1] - hand_list[i]
        else:
            ans = hand_list[i + 2 * k] - hand_list[i]
        ans_list.append(ans)
else:
    ans_list.append(n)
print(max(ans_list))

### FIXED CODE ###

n, k = map(int, input().split())
s = input()
hand_list = []
for i in range(n):
    if i == 0:
        hand_list.append(i)
    else:
        if s[i] != s[i - 1]:
            hand_list.append(i)
hand_list.append(n)

ans_list = []
if len(hand_list) > 2 * k:
    for i in range(len(hand_list) - 2 * k):
        if s[hand_list[i]] == '1':
            ans = hand_list[min(i + 2 * k + 1, len(hand_list)-1)] - hand_list[i]
        else:
            ans = hand_list[i + 2 * k] - hand_list[i]
        ans_list.append(ans)
else:
    ans_list.append(n)
print(max(ans_list))
import math 
N, X = map(int, input().split())
l = list(map(int, input().split()))

l.insert(0, X)
diff_list = [0] * (int(len(l)/2) + 1)

ans = abs(l[0] - l[1])
ix = 2
for i in l[1:len(l)-1]:
    tmp = abs(i - l[ix])
    ans = math.gcd(ans, tmp)
    ix += 1
print(ans)

### FIXED CODE ###


N, X = map(int, input().split())
l = list(map(int, input().split()))

l.insert(0, X)
diff_list = [0] * (int(len(l)/2) + 1)

ans = abs(l[0] - l[1])
ix = 2

#a,bの最大公約数
def gcd(a,b):
    if b == 0:
        return a
    else:
        return gcd(b,a%b)

for i in l[1:len(l)-1]:
    tmp = abs(i - l[ix])
    ans = gcd(ans, tmp)
    ix += 1
print(ans)
s=input()
ans=0
num=0
while num<len(s)-1:
    if s[num]!=s[num+1]:
        s=s[:num]+s[num+2:]
        num-=1
        ans+=2
    else:
        num+=1
print(ans)

### FIXED CODE ###

s=input()
print(2*min(s.count("0"), s.count("1")))
from fraction import gcd

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

sortedA = sorted(A)
answer = A[0]

for x in range(0,N):
        answer = gcd(answer,A[x])
        if answer == 1:
            break

print(answer)

### FIXED CODE ###

from fractions import gcd

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

sortedA = sorted(A)
answer = A[0]

for x in range(0,N):
        answer = gcd(answer,A[x])
        if answer == 1:
            break

print(answer)
N, K = map(int, input().split())
H = [int(i) for i in input().split()]

inf = float('inf')
dp = [inf] * N
dp[0] = 0

for i in range(1, N):
    for k in range(1, K + 1):
        dp[i] = min(dp[i], dp[i - k] + abs(H[i] - H[i - k]))
    
print(dp[-1])

### FIXED CODE ###

import numpy as np

n, k = map(int, input().split())
H = np.array(list(map(int, input().split())))
dp = np.zeros(n, dtype = int)

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