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

import copy

def movable_state(state):
    x, y = None, None
    for i in range(3):
        for j in range(3):
            if state[i][j] == 0:
                x, y = i, j
                break

    rsts = []
    for r, c in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]:
        if 0 <= r and r < 3 and 0 <= c and c < 3:
            rst = copy.deepcopy(state)
            rst[x][y], rst[r][c] = rst[r][c], rst[x][y]
            rsts.append(rst)
    return rsts

def hist_check(state, depth):
    for i in range(depth-1):
        for hist in state_history[i]:
            if hist == state:
                return True
    return False

puzzle = [list(map(int, input().split(' '))) for i in range(3)]
state_history = [[puzzle]]

goal = [[1, 2, 3], [4, 5, 6], [7, 8, 0]]
exchange_num = 0
depth = 0
still_not = True
while still_not:
    depth += 1
    state_history.append([])
    for hist in state_history[depth-1]:
        next_states = movable_state(hist)
        for next_stat in next_states:
            if hist_check(next_stat, depth): continue
            if next_stat == goal:
                still_not = False
                break
            state_history[depth].append(next_stat)
        if not still_not: break
print(depth)



### FIXED CODE ###

from collections import deque, OrderedDict

class Puzzle:
    def __init__(self, field=None, path=''):
        self.f = field
        self.space = None
        for i in range(9):
            if self.f[i] == 9:
                self.space = i
        self.path = path

    def __lt__(self, pzl): # <
        for i in range(9):
            if self.f[i] == pzl.f[i]:
                continue
            return self.f[i] > pzl.f[i]
        return False

    def __gt__(self, pzl): # >
        for i in range(9):
            if self.f[i] == pzl.f[i]:
                continue
            return self.f[i] < pzl.f[i]
        return False

dx = [-1, 0, 1, 0]
dy = [0, -1, 0, 1]
dir = ['u', 'l', 'd', 'r']

def is_target(pzl):
    for i in range(9):
        if pzl.f[i] != i+1:
            return False
    return True

def bfs(pzl):
    queue = deque([])
    V = {}
    pzl.path = ''
    queue.append(pzl)
    V[str(pzl.f)] = True
    if is_target(pzl): return pzl.path

    while len(queue) != 0:
        u = queue.popleft()
        sx, sy = u.space//3, u.space%3
        for r in range(4):
            tx, ty = sx + dx[r], sy + dy[r]
            if tx < 0 or ty < 0 or tx >= 3 or ty >= 3:
                continue
            v = Puzzle(field=[u.f[i] for i in range(9)], path=u.path)
            v.f[u.space], v.f[tx*3+ty] = v.f[tx*3+ty], v.f[u.space]
            v.space = tx*3 + ty
            if str(v.f) not in V:
                V[str(v.f)] = True
                v.path += dir[r]
                if is_target(v): return v.path
                queue.append(v)
    return 'unsolvable'

field = []
for i in range(3):
    field.extend(list(map(int, input().split(' '))))

for i in range(9):
    if field[i] == 0: field[i] = 9

pzl = Puzzle(field=field)
ans= bfs(pzl)
print(len(ans))
### BUGGY CODE ###

N, K= map(int, input().split())
h = list(map(int, input().split()))
import numpy as np
dp = np.full((N+1, K+1), np.inf, dtype=float)
dp[1] = np.zeros(K+1)
for i in range(1, N):
    k = 1
    while i >= k and k <= K:
        dp[i+1][k] = abs(h[i] - h[i - k]) + min(dp[i + 1 - k])
        k += 1
print(int(min(dp[N])))




### FIXED CODE ###

N, K= map(int, input().split())
h = list(map(int, input().split()))
dp = [0]*(N+1)
for i in range(1, N):
    dp[i+1] = min(
        [
            abs(h[i]-h[i-k]) + dp[i+1-k]
            for k in range(1, min(K, i)+1)
        ]
    )
print(dp[N])
### BUGGY CODE ###

N, K = map(int,input().split())
S = input()

ss = []
pre = S[0]
num = 0
if S[0]=='0':ss.append(0)
  
for i in range(1, N):
    if S[i]!=pre:
        ss.append(len(S[num:i]))
        num = i
        pre = S[i]
ss.append(len(S[num: N]))

ans = []

for i in range(0,len(ss), 2):
    ans.append(sum(ss[i:i+2*K+1]))
    if i+2*K+1> len(ss):break

print(max(ans))
  


### FIXED CODE ###

N, K = map(int,input().split())
S = input()
s = []
if S[0]=='0':s = [0]
for x in S.replace('01', '0,1').replace('10','1,0').split(','):
    s.append(len(x))
M = len(s)
ans = [0] * M
ans[0] = sum(s[:2*K+1])

for i in range(2, M, 2):
    ans[i] = ans[i-2] - s[i-2] - s[i-1] + sum(s[min(i+2*K-1,M):i+2*K+1])
print(max(ans))
### BUGGY CODE ###

def main():
    N, K  = [int(i) for i in input().split()]
    A  = [int(i) for i in input().split()]
    v = [0] * N
    r = 0
    for i, a in enumerate(A, 1):
        for j in range(i):
            v[j] = t = (v[j] + a) % K
            if t == i - j:
                r += 1
    return(r)


print(main())


### FIXED CODE ###

def main():
    N, K  = [int(i) for i in input().split()]
    A  = [int(i) for i in input().split()]
    v = {0: 1}
    n = [0]
    r = 0
    t = 0
    for i, a in enumerate(A, 1):
        if i >= K:
            v[n[i - K]] -= 1
        t += a
        j = (t - i) % K
        r += v.get(j, 0)
        v[j] = v.get(j, 0) + 1
        n.append(j)

    return r


print(main())
### BUGGY CODE ###

n,m=map(int,input().split())
a=list(map(int,input().split()))
for i in range(m):
    b,c=map(int,input().split())
    a+=[c]*b
a=sorted(a)
print(sum(a[-n:]))

### FIXED CODE ###

n,m=map(int,input().split())
a=sorted(list(map(int,input().split())))[::-1]
k=sorted([list(map(int,input().split()))for i in range(m)],key=lambda x:-x[1])+[[0,0]]
c,d=0,0
t=0
ans=0
while c<n:
    if a[d]>=k[t][1]:
        ans+=a[d]
        d+=1
        c+=1
    else:
        ans+=k[t][1]*min(n-c,k[t][0])
        c+=k[t][0]
        t+=1
print(ans)
### BUGGY CODE ###

import math

r = 50001
sqrt = int(math.sqrt(r))
p = [1]*r
p[0] = 0
for i in range(1,sqrt):
    if p[i]:
        p[2*i+1::i+1] = [0 for x in range(2*i+1,r,i+1)]

while True:
    n = int(raw_input())
    if n == 0:
        break
    count = 0
    for i in range(n/2):
        if p[i] == 1:
            m = n - (i+1)
            if p[m-1] == 1:
                count += 1
    print count

### FIXED CODE ###

import math

r = 50001
sqrt = int(math.sqrt(r))
p = [1]*r
p[0] = 0
for i in range(1,sqrt):
    if p[i]:
        p[2*i+1::i+1] = [0 for x in range(2*i+1,r,i+1)]

prime = []
for i in range(len(p)):
    if p[i] == 1:
        prime.append(i+1)

while True:
    n = int(raw_input())
    if n == 0:
        break
    count = 0
    for i in prime:
        if i > n/2:
            break
        m = n - i
        if p[m-1] == 1:
                count += 1
    print count
### BUGGY CODE ###

N, M = map(int, input().split())
mae = 0
sub = []
flag = False

for _ in range(M):
  broken = int(input())
  if mae == broken: # 不可能
    flag = True
  if flag:
    continue
  if mae+1 == broken:
    mae = broken + 1
    continue
  sub.append(broken-1-mae)
  mae = broken + 1
# 無理な時
if flag:
  print(0)
  exit()
# forの中で最後まで行ってない分の追加
if mae != N:
  sub.append(N-mae)

from operator import mul
from functools import reduce

# nCrの関数
def C(n, r):
    r = min(r, n - r)
    numer = reduce(mul, range(n, n - r, -1), 1)
    denom = reduce(mul, range(1, r + 1), 1)
    return numer // denom
# 壊れてるやつの間の上り方の場合の数
def count(n):
  ans = 1
  for i in range(n//2):
    ans += C(n-i-1, i+1)
  return ans

ans = 1
waru = 10**9+7
for s in sub:
  ans *= count(s)%waru
print(ans%waru)

### FIXED CODE ###

N, M = map(int, input().split())
A = [True]*N
for _ in range(M):
  a = int(input())
  A[a-1] = False # 壊れてるところはfalse

waru = 10**9 + 7
dp = [0]*(N+1)

dp[0], dp[1] = 1, 1 # 初期条件
if not A[0]: # 1段目が壊れてたら
  dp[1] = 0

for i in range(2,N+1):
  # 壊れてるところはdp=0にする
  if not A[i-1]:
    dp[i] = 0
  else:
    dp[i] = (dp[i-1] + dp[i-2])%waru
print(dp[-1])
### BUGGY CODE ###

N,W=map(int,input().split())
dp=[0]*(W+1)
for i in range(N):
    w,v=map(int,input().split())
    for j in range(W,w-1,-1):
        dp[j]=max(dp[j],dp[j-w]+v)
print(dp[-1])

### FIXED CODE ###

from numpy import *
N,W=map(int,input().split())
dp=zeros(W+1,dtype=int)
for i in range(N):
    w,v=map(int,input().split())
    dp[w:]=maximum(dp[:W-w+1]+v,dp[w:])
print(dp[-1])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
N = int(input())
A_list = list(map(int, input().split()))
ans = 1
for i in range(N):
    ans *= A_list[i]

print(-1 if ans > 10 ** 18 else ans)

### FIXED CODE ###

# -*- coding: utf-8 -*-
N = int(input())
A_list = list(map(int, input().split()))

if A_list.count(0) > 0:
    print(0)
else:
    ans = 1
    for i in range(N):
        ans *= A_list[i]
        if ans > 10 ** 18:
            print(-1)
            break
    else:
        print(ans)
### BUGGY CODE ###

n = int(input())
L = sorted([int(i) for i in input().split()],reverse=True)
a = []
for l in L:
  if L.count(l) >= 4 and a==[]:
    print(l*l)
    exit()
  elif L.count(l)>=2 and l not in a:
    a.append(l)
    if len(a) == 2:
      break
print(0 if a==[] else a[0]*a[1])



### FIXED CODE ###

from collections import defaultdict
N = int(input())
A = [int(i) for i in input().split()]
d = defaultdict(int)
for a in A:
  d[a] += 1
x = 1
cnt = 0
d = sorted(d.items(), key=lambda x:-x[0])
for i, j in d:
  if x == 1 and j >= 4:
    print(i**2)
    exit()
  if j >= 2:
    x *= i
    cnt += 1
    if cnt == 2:
      break
if cnt >= 1:
  print(x)
else:
  print(0)
### BUGGY CODE ###

import copy
import numpy as np

N = int(input())
A = []
B = []

for _ in range(N):
    putin = int(input())
    A.append(putin)
    B.append(putin)

for i in range(N):
    A = copy.deepcopy(B)
    del A[i]
    print(np.max(A))

### FIXED CODE ###


import numpy as np

N = int(input())
A = []
B = []

for _ in range(N):
    putin = int(input())
    A.append(putin)
    B.append(putin)

MAX = int(np.max(A))
A.remove(MAX)
MAX2 = int(np.max(A))

for i in range(N):
    if B[i] == MAX:
        print(MAX2)
    
    else:
        print(MAX)
### BUGGY CODE ###

while True:
  h,w,n = map(int,input().split())
  if not h: break
  sss = [[True if s == "1" else False for s in input().split()] for i in range(h)]
  for i in range(n):
    x = y = 0
    while x < h and y < w:
      sss[x][y] = not sss[x][y]
      if sss[x][y]:
        x += 1
      else:
        y += 1
  print(x + 1,y + 1)



### FIXED CODE ###

def solve():
  while True:
    h,w,n = map(int,input().split())
    if not h: break
    mp = [[int(s) for s in input().split()] for i in range(h)]
    dp = [[0 for i in range(w + 1)] for j in range(h + 1)]
    dp[0][0] = n - 1
    for x in range(h):
      dpx = dp[x]
      dpxp = dp[x + 1]
      mpx = mp[x]
      for y in range(w):
        a = dpx[y]
        b = mpx[y]
        if b:
          if a % 2:
            dpxp[y] += a // 2
            dpx[y + 1] += a // 2 + 1
          else:
            dpxp[y] += a // 2
            dpx[y + 1] += a // 2
        else:
          if a % 2:
            dpxp[y] += a // 2 + 1
            dpx[y + 1] += a // 2
          else:
            dpxp[y] += a // 2
            dpx[y + 1] += a // 2
        mpx[y] = (a + b) % 2
  
    x = y = 0
    while x < h and y < w:
      if mp[x][y]:
        y += 1
      else:
        x += 1
    print(x + 1,y + 1)
solve()
### BUGGY CODE ###

import sys
import numpy as np

def IL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def main():
	N, K = IL()
	h_i = IL()
	dp = np.full((N,), np.inf)
	dp[0] = 0
	for i in range(N):
		for j in range(1, K+1):
			if i+j < N:
				dp[i+j] = np.min([dp[i+j], abs(h_i[i] - h_i[i+j]) + dp[i]])
		
	print(int(dp[-1]))


if __name__ == "__main__":
	main()

### FIXED CODE ###

import sys
import numpy as np

def LI():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def main():
	N, K = LI()
	h_i = np.array(LI())
	dp = np.full(N, 10**10, dtype=int)
	dp[0] = 0
	for i in range(1, N):
		dp[i:i+K] = np.fmin(dp[i:i+K], dp[i-1] + np.abs(h_i[i:i+K] - h_i[i-1]))
		
	return dp[-1]


if __name__ == "__main__":
	print(main())
### BUGGY CODE ###

import numpy as np
n=int(input())
a=[int(i) for i in input().split()]



def count(num_list):
    l=len(num_list)
    num_array=np.array(num_list[1:])
    check=np.array(range(1,l))-num_list[0]
    ans=num_array-check
    return l-np.count_nonzero(ans)-1
ans=0
for i in range(0,n-1):
    check_list=a[i:]
    ans+=count(check_list)
print(ans)

### FIXED CODE ###

n = int(input())
a = [int(i) for i in input().split()]

j_Aj = [0]

for j, aj in enumerate(a):
    j_Aj.append(j + 1 - aj)
maxj=max(j_Aj)
i_Ai = [0] * (maxj+1)
ans = 0
for j, j_aj in enumerate(j_Aj):
    if j == 0:
        continue
    if j_aj >= 2:
        ans += i_Ai[j_aj]
    if j + a[j - 1]<=maxj:
        i_Ai[j + a[j - 1]] += 1
print(ans)
### BUGGY CODE ###

N,K = map(int,input().split())
AB =[]
for n in range(N):
    a,b = map(int,input().split())
    AB.extend([a]*b)
print(sorted(AB)[K-1])

### FIXED CODE ###

N,K = map(int,input().split())
AB =[]
for n in range(N):
    a,b = map(int,input().split())
    AB.append([a,b])
AB.sort(key=lambda x:x[0])
cnt = 0
for i,a in enumerate(AB):
    if cnt < K:
        cnt +=a[1]
    if cnt >=K:
        print(a[0])
        exit()
### BUGGY CODE ###

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

ans = float('inf')

if A + B >= 2 * C:
    p = (2 * max(X, Y)) * C
    ans = min(ans, p)

for x in range(X + 1):
    for y in range(Y + 1):
        c = max(X - x, Y - y)
        p = x * A + y * B + (2 * c) * C
        ans = min(ans, p)

print(ans)

### FIXED CODE ###

a, b, c, x, y = map(int, input().split())

normal_price = a * x + b * y
min_price = float('inf')
minn = min(x, y)
maxx = max(x, y)

for mi in range(2, maxx * 2 + 1, 2):
    mix_price = c * mi
    xz = x - mi // 2
    yz = y - mi // 2
    if xz < 0: xz = 0
    if yz < 0: yz = 0
    x_price = xz * a
    y_price = yz * b
    total_price = mix_price + x_price + y_price
    min_price = min(min_price, total_price)

min_price = min(min_price, normal_price)
print(min_price)
### BUGGY CODE ###

from collections import defaultdict


s = input()
n = len(s)

dd = defaultdict(int)

# d = [0] * 2019
dd[0] = 1
tmp = 0
_10 = 1
# print(s, n)
for i in range(n - 1, -1, -1):
    # print(i, s[i])
    tmp = tmp + int(s[i]) * _10
    _10 *= 10
    # print(tmp, tmp % 2019)
    dd[tmp % 2019] += 1

# print(dd)
print(sum(v*(v-1)//2 for v in dd.values()))


### FIXED CODE ###

import math
s = input()
n = len(s)
count = 0
a = [0 for i in range(2019)]
a[0] = 1
k = 0
b = [0 for i in range(n)]
b[0] = 1
for i in range(1, n):
    b[i] = b[i-1]*10 % 2019

#print(b)
for i in reversed(range(0, n)):
 #   print((b[n-i-1])*int(s[i]) % 2019)
    k += (b[n-i-1])*int(s[i]) % 2019
  #  print(k, k % 2019)
    a[k % 2019] += 1

for i in range(len(a)):
    if a[i] >= 2:
        count += (a[i])*(a[i]-1)//2
print(count)
### BUGGY CODE ###

N = int(input())
S = list(input())
S2=[]
R = 0
G = 0
B = 0

for x in range(N):
    if S[x] =="R":
        R +=1
        S2.append(["R",R])
    elif S[x] =="G":
        G +=1
        S2.append(["G",G])
    else:
        B +=1
        S2.append(["B",B])
ans =0
a = 0
b =0
for x in range(N):
    i = S2[x][0]
    for y in range(x,N):
        j = S2[y][0]
        if j != i:
            if j =="R":
                a =R-S2[y][1]+1
            elif j =="G":
                a =G-S2[y][1]+1
            else:
                a =B-S2[y][1]+1
            for z in range(x,N):
                k = S2[z][0]
                if k != i and k != j:
                    if k =="R":
                        b =R-S2[z][1]+1
                    elif k =="G":
                        b =G-S2[z][1]+1
                    else:
                        b =B-S2[z][1]+1
                    break
            else:
                b = 0
            break
    else:
        a = 0
    ans +=a*b
subn =0
for x in range(N):
    i = S2[x][0]
    for y in range(x,N):
        j = S2[y][0]   
        if j != i:
            d = y-x
            if y+d<N:
                if i!= S2[y+d][0] and j!=S2[y+d][0]:
                    subn +=1
            else:
                break
print(ans-subn)

### FIXED CODE ###

N = int(input())
S = list(input())
S2=[]
R = 0
G = 0
B = 0

for x in range(N):
    if S[x] =="R":
        R +=1
        S2.append(["R",R])
    elif S[x] =="G":
        G +=1
        S2.append(["G",G])
    else:
        B +=1
        S2.append(["B",B])
ans =0
a = 0
b =0
for x in range(N):
    i = S2[x][0]
    for y in range(x,N):
        j = S2[y][0]
        if j != i:
            if j =="R":
                a =R-S2[y][1]+1
            elif j =="G":
                a =G-S2[y][1]+1
            else:
                a =B-S2[y][1]+1
            for z in range(x,N):
                k = S2[z][0]
                if k != i and k != j:
                    if k =="R":
                        b =R-S2[z][1]+1
                    elif k =="G":
                        b =G-S2[z][1]+1
                    else:
                        b =B-S2[z][1]+1
                    break
            else:
                b = 0
            break
    else:
        a = 0
    ans +=a*b
subn =0
for x in range(N):
    i = S2[x][0]
    for y in range(x,N):
        j = S2[y][0]   
        if j != i:
            d = y-x
            if y+d<N:
                if i!= S2[y+d][0] and j!=S2[y+d][0]:
                    subn +=1
            else:
                break
print(ans-subn)
### BUGGY CODE ###




# -*- coding: utf-8 -*-
"""
Created on Thu Jan 31 03:17:55 2019

@author: rubug
"""

# -*- coding: utf-8 -*-
# 整数の入力
import numpy as np

N,Q = map(int,input().split())
s = str(input())
S = []
for c in s:
    S.append(c)

for i in range(Q):
    l, r = map(int, input().split())
    lst = S[int(l-1):int(r)]
    count = 0
    for i in range(len(lst)-1):
        if (lst[i] == "A")and(lst[i+1] == "C"):
            count += 1
    print(count)
            
        
    
    
    





### FIXED CODE ###





import numpy as np

N,Q = map(int,input().split())
S = []
for c in str(input()):
    S.append(c)

a = np.zeros(N)
   
for i in range(1,N):
    if (S[i-1] == "A")and(S[i] == "C"):
        a[i] = a[i-1] + 1
    else:
        a[i] = a[i-1]
        
for i in range(Q):
    l, r = map(int, input().split())
    print(int(a[r-1] - a[l-1]))
### BUGGY CODE ###

import sys
# from collections import defaultdict

N = int(sys.stdin.readline().rstrip())
S = sys.stdin.readline().rstrip()
Q = int(sys.stdin.readline().rstrip())

BIT = [[0 for _ in range(N + 1)] for _ in range(26)]  # 初期化（アルファベット分）
alpha = {"a": 0, "b": 1, "c": 2, "d": 3, "e": 4,
         "f": 5, "g": 6, "h": 7, "i": 8, "j": 9,
         "k": 10, "l": 11, "m": 12, "n": 13, "o": 14,
         "p": 15, "q": 16, "r": 17, "s": 18, "t": 19,
         "u": 20, "v": 21, "w": 22, "x": 23, "y": 24, "z": 25}


# 初期化
def initialize():
    global BIT, S, N
    for j in range(N):
        c = alpha[S[j]]  # 文字切り出し／index に変換
        i = j + 1
        while i <= N:
            BIT[c][i] += 1
            i += (i & -i)


def identify(i):
    # i文字目を、変化点があった文字として探索する
    for c in range(26):
        if sum(i, c) != sum(i - 1, c):
            return c


# 文字の交換
def change(i, before, after):

    global BIT, N
    while i <= N:
        BIT[before][i] -= 1
        BIT[after][i] += 1
        i += (i & -i)


# 文字数の取り出し
def sum(i, c):

    global BIT

    _sum = 0
    while i > 0:
        _sum += BIT[c][i]
        i -= (i & -i)

    return _sum


initialize()

for _ in range(Q):
    q, x, y = sys.stdin.readline().rstrip().split()
    if q == "1":
        i = int(x)
        ac = alpha[y]
        bc = identify(i)
        change(i, bc, ac)

    else:
        x = int(x)
        y = int(y)
        count = 0
        for c in range(26):
            if sum(y, c) != sum(x - 1, c):
                count += 1
        print(count)

### FIXED CODE ###

import sys
# from collections import defaultdict

N = int(sys.stdin.readline().rstrip())
S = sys.stdin.readline().rstrip()
Q = int(sys.stdin.readline().rstrip())

BIT = [[0 for _ in range(N + 1)] for _ in range(26)]  # 初期化（アルファベット分）
alpha = {"a": 0, "b": 1, "c": 2, "d": 3, "e": 4,
         "f": 5, "g": 6, "h": 7, "i": 8, "j": 9,
         "k": 10, "l": 11, "m": 12, "n": 13, "o": 14,
         "p": 15, "q": 16, "r": 17, "s": 18, "t": 19,
         "u": 20, "v": 21, "w": 22, "x": 23, "y": 24, "z": 25}


# 初期化
def initialize():
    global BIT, S, N
    for j in range(N):
        c = alpha[S[j]]  # 文字切り出し／index に変換
        i = j + 1
        while i <= N:
            BIT[c][i] += 1
            i += (i & -i)


def identify(i):
    # i文字目を、変化点があった文字として探索する
    for c in range(26):
        if sum(i, c) != sum(i - 1, c):
            return c


# 文字の交換
def change(i, before, after):

    global BIT, N
    while i <= N:
        BIT[before][i] -= 1
        BIT[after][i] += 1
        i += (i & -i)


# 文字数の取り出し
def sum(i, c):

    global BIT

    _sum = 0
    while i > 0:
        _sum += BIT[c][i]
        i -= (i & -i)

    return _sum


initialize()

for _ in range(Q):
    q, x, y = sys.stdin.readline().rstrip().split()
    if q == "1":
        i = int(x)
        ac = alpha[y]
        bc = identify(i)
        change(i, bc, ac)

    else:
        x = int(x)
        y = int(y)
        count = 0
        for c in range(26):
            if sum(y, c) != sum(x - 1, c):
                count += 1
        print(count)
### BUGGY CODE ###

n = int(input())
s = []
for _ in range(n):
    s.append(input())

sdict = []
for x in s:
    tmp = {}
    for y in x:
        if y in tmp:
            tmp[y] += 1
        else:
            tmp[y] =1
    sdict.append(tmp)
cnt = 0
for i in range(n-1):
    for j in range(i+1,n):
        if sdict[i] == sdict[j]:
            cnt += 1
print(cnt)


### FIXED CODE ###

n = int(input())
s = []
for _ in range(n):
    tmp = list(input())
    tmp.sort()
    s.append(str(tmp))
cnt = 0
dict = {}
for x in s:
    if x in dict:
        cnt += dict[x]
        dict[x] += 1
    else:
        dict[x] = 1
print(cnt)
### BUGGY CODE ###

import sys
t = sys.stdin.readlines()
N,K = map(int, t[0].split())
S = []
for i in range(K):
    L,R = map(int, t[1+i].split())
    S += [ j for j in range(L,R+1)]

S = sorted(S)

step = [0]*(N+1)
step[1] = 1


for j in range(1,N):
    for s in S:
        if j + s > N or step[j] == 0:
            continue
        step[j+s] += (step[j]%998244353)
        step[j+s] %= 998244353
    
print(step[N])

### FIXED CODE ###

mod = 998244353
n, k = map(int, input().split())
lr = [list(map(int, input().split())) for i in range(k)]
for i in range(k):
    lr[i][1] += 1

dp = [0]*n
dp[0] = 1
for i in range(1,n):
    dp[i] = dp[i-1]
    if i == 1:
        dp[1] = 0
    for l,r in lr:
        if i - l >= 0:
            dp[i] += dp[i-l]
        if i - r >= 0:
            dp[i] -= dp[i-r]
        dp[i] %= mod
print(dp[n-1])
### BUGGY CODE ###

import collections
import sys
input = sys.stdin.readline
from array import array
def solve():
  n = int(input())
  query2 = collections.deque([])
  ans = array('I', [ 0 for i in range(n)])
  for i in range(n-1):
    a,b = (int(i) for i in input().split())
    query2.append(a)
    query2.append(b)
    
  c = list(int(i) for i in input().split())
  c = sorted(c,reverse =True)
  
  d = collections.Counter(query2)

  for i in range(n):
    ans[d.most_common()[i][0]-1] = c[i]
    
  print(sum(c) +(-1)*max(c))
  #dの処理
  print(*ans)
  
solve()

### FIXED CODE ###

import collections
import sys
input = sys.stdin.readline
import heapq
from array import array
def solve():
  n = int(input())

  query2 = collections.deque([])
  edge = [[] for _ in range(n)]
  ans = array('I', [ 0 for i in range(n)])
  for i in range(n-1):
    a,b = (int(i) for i in input().split())
    query2.append(a)
    query2.append(b)
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)
  c = list(int(i) for i in input().split())
  if n == 1:
    print(1)
    print(c[0])
    exit()
  c = collections.deque(sorted(c,reverse =True))
  d = collections.Counter(query2)
  d2 = d.most_common()
  bfs = []
  heapq.heappush(bfs,(-1*d2[0][1],d2[0][0]-1,-1))#回数,場所、親
  ct = 0
  visit = [False]*n
  while bfs:
    times,place,parent = heapq.heappop(bfs)
    if visit[place]:
      continue
    else:
      visit[place] = True

      for i in range(len(edge[place])):
        newp = edge[place][i]
        newtimes = len(edge[newp])
        if not visit[newp]:
          heapq.heappush(bfs,(-1*newtimes,newp,place))
      #print(place,parent,times)
      ans[place] = c.popleft()

      #print(c,place)

  print(sum(ans)-max(ans))
  print(*ans)
  
solve()